Set summed with itself

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Set summed with itself

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Awesomemath Sample Problems

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Math-Problem-Solving

65 posts

Math-Problem-Solving

#1 h Apr 16, 2025, 1:59 AM

Y by

Let $A = \{1, 4, \ldots, n^2\}$ be the set of the first $n$ perfect squares of nonzero integers. Suppose that $A \subset B + B$ for some $B \subset \mathbb{Z}$ . Here $B + B$ stands for the set $\{b_1 + b_2 : b_1, b_2 \in B\}$ . Prove that $|B| \geq |A|^{2/3 - \epsilon}$ holds for every $\epsilon > 0$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi_quadrat_sechstel

586 posts

pi_quadrat_sechstel

#2 h Apr 16, 2025, 5:25 PM • 1 Y

Y by internationalnick123456

Math-Problem-Solving wrote:

Let $A = \{1, 4, \ldots, n^2\}$ be the set of the first $n$ perfect squares of nonzero integers. Suppose that $A \subset B + B$ for some $B \subset \mathbb{Z}$ . Here $B + B$ stands for the set $\{b_1 + b_2 : b_1, b_2 \in B\}$ . Prove that $|B| \geq |A|^{2/3 - \epsilon}$ holds for every $\epsilon > 0$ .

Consider a graph with $B$ as the set of vertices and exactly one edge (potentially a loop) connecting two elements with sum $k^2$ for $1\leq k\leq n$ . For every path of length $2$ the difference of the two ends is the difference of the squares corresponding to the edges. We will count the number of paths of length $2$ in two different ways.

First, for a number $m$ there are at most as many ways to write $m$ as a difference of squares as there are divisors of $m$ since $m=a^2-b^2$ is equivalent to $m=(a+b)(a-b)$ . But for $\tilde{\varepsilon}=3\varepsilon>0$ , there are $O\left(n^{\tilde{\varepsilon}}\right)$ divisors for every positive integer $n$ . So there are $O\left(|B|^2n^{3\varepsilon}\right)$ paths of length $2$ in the graph.

Second, there are $\sum_{v\in B}\frac{d_v(d_v-1)}{2}\geq|B|\cdot\frac{\frac{\sum_{v\in B}d_v}{|B|}\left(\frac{\sum_{v\in B}d_v}{|B|}-1\right)}{2}=|B|\cdot\frac{\frac{2n}{|B|}\left(\frac{2n}{|B|}-1\right)}{2}=\Omega\left(\frac{n^2}{|B|}\right)$ paths of length $2$ in the graph where $d_v$ is the degree of $v$ . (Here we use Jensen's on the convex function $\frac{x(x-1)}{2}$ .)

So the number of length $2$ paths is in both $O\left(|B|^2n^{3\varepsilon}\right)$ and $\Omega\left(\frac{n^2}{|B|}\right)$ . So $|B|$ must be in $\Omega\left(n^{\frac{2}{3}-\varepsilon}\right)$ for every $\varepsilon>0$ .

This post has been edited 4 times. Last edited by pi_quadrat_sechstel, Apr 18, 2025, 10:20 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a