For a set $A$ of integers, define $f(A)=\{x^2+xy+y^2: x,y\in A\}$. Is there a constant $c$ such that for all positive integers $n$, there exists a set $A$ of size $n$ such that $|f(A)|\le cn$? David Yang.
Problem
Source: ELMO Shortlist 2012, C9
Tags: analytic geometry, geometry, geometric transformation, combinatorics, number theory
02.07.2012 06:40
¿What is ELMO?
24.10.2012 15:44
No, such constant does not exist. Proof /a brief outline/ Let on the contrary assume that there exists a constant $c$ such that for all $n$ exists a set $A,\, |A|=n,\, |f(A)| \leq cn$. See that $x^2+xy+y^2= \frac{x^3-y^3}{x-y}$. So we can restate the assertion as follows. For each $n$ we can find a set with $n$ points $A=\{A_1,A_2,\ldots, A_n\}$ on a plane, lying on the curve $y=x^3$, with integer $x$-coordinates, so that the set of the lines spanned by $A$ forms at most $cn$ different directions(slopes). Below we give up the requirement that the points have integer $x$-coordinates. Further we use the notion of allowable sequences, introduced by Goodman and Pollack. Below I make a quotation from http://library.msri.org/books/Book52/files/22last.pdf where this notion is defined. ... "Let $A$ be a set of $n$ points in the plane, let $L$ be the set of the lines spanned by $A$, and let $\{ k_1, k_2, \ldots, k_m \}$ be the $m$ different slopes of the lines according to a fixed coordinate system. We choose a directed line $l$ in the plane with a point $P$ on it, such that $l$ does not contain any point of $A$ and is not orthogonal to any line in $L$. Here is the construction of ${\mathcal{A}_{l,P}(A)}$, the allowable sequence of permutations of a point set $A$, according to the directed line $l$ and the point $P$: We label the points of $A$, according to their orthogonal projection on $l$ and we get the first permutation $\pi_0 = 1, . . . , n$. Let $l$ rotate counterclockwise around $P$ by $180^o$ and look at the orthogonal projections of the labeled points of $A$ on $l$ as it rotates. A new permutation arises whenever $l$ passes through a direction orthogonal to one of the slopes $k_1, k_2, . . . , k_m$. It follows that along the course of this rotation, beside $\pi_0$, we will get $m$ different permutations: $\pi_1, . . . , \pi_m$. Define ${\mathcal{A}_{l,P}(A)} = \{\pi_0, \pi_1, \pi_2, . . . , \pi_m\}$. For each $1 \leq i \leq m$, whenever $l$ passes through a direction orthogonal to $k_i$, the new permutation that arises differs from the previous one by reversing the order of the consecutive elements whose corresponding points of A lie on a line of slope $k_i$. Such reversed consecutive elements are called a reversed substring. If $t$ lines in $L$ have a slope equal to $k_i$, the permutation that corresponds to $k_i$ has $t$ disjoint reversed substrings. A reversed substring of length $2$ is called a simple switch"... In our case all reversed substrings are simple disjoint switches. We can start with $l$ to be the $x$-coordinate axe. Let in the first moment the permutation is: $x_1,x_2,\ldots, x_n$. Due to convexity of $y=x^3$ it can be shown that reversing any of $x_1,x_2,\ldots,x_i$ can't start before any point of the rest: $x_{i+1},\ldots, x_n$ is still to the right of $x_i$. Reversing in our case resembles turning a sleeve inside out. Consider points $x_1,x_2,\ldots,x_{\lfloor \frac{n}{2} \rfloor}$, they are fixed when the rest of the points in order $x_n,x_{n-1},\ldots,x_{\lfloor \frac{n}{2} \rfloor +1} $ will pass through them in at most $cn$ moments. Denote by $\Gamma$ all segments $[x_i,x_j], i,j=1,2,\ldots \frac{n}{2}$, by $\Gamma' $ all segments with ends in $x_n,x_{n-1},\ldots,x_{\lfloor \frac{n}{2} \rfloor +1}$, by $\Gamma(d)$ all segments in $\Gamma$ with length at most $d$, (i.e. $|i-j| \leq d $), similarly is defined $\Gamma'(d)$. Notice that $|\Gamma(d)|=O(n),\, |\Gamma'(d)|=O(n). $ You can imagine that the segments of $\Gamma'$ move, while the segments of $\Gamma$ stay fixed. We say that a segment in $\Gamma'$ moves over a segment in $\Gamma$ if the two ends of the first segment simultaneously make switch with the two ends of the second segment. The following claims hold and could be proven one after another: 1) There exists an absolute constant $d$ (depending on $c$), such that there exist $\Omega(n)$ moments and at each of them $\Omega(n)$ segments of $\Gamma'(d)$ move simultaneously over respective segments of $\Gamma(d)$. 2) There are $\Omega(n)$ segments in $\Gamma'(d)$ such that for every one of them exist $\Omega(n)$ moments and in each of these moments the segment moves over some segment in $\Gamma(d)$. 3) There exist different $s'_1, s'_2 \in \Gamma'(d),\, s_1,s_2 \in \Gamma(d)$ such that in some moments $s'_1$ moves over $s_1$ and $s_2$ and in some other moments $s'_2$ moves over $s_1$ and $s_2$ Here we stop with combinatorics and take into account the concrete curve $y=x^3$ our points lie on. 3) means that there exist points $A_1, B_1, A_2,B_2, A'_1, B'_1, A'_2, B'_2$ on $y=x^3$ such that 4) $A_1A'_1 \parallel B_1B'_1,\, A_2A'_1 \parallel B_2B'_1,\, A_1A'_2 \parallel B_1B'_2,\, A_2A'_2 \parallel B_2B'_2 $ The last claim is impossible, thou I admit that did not check it carefuly.
26.10.2012 06:36
Interesting solution, is the last step really trivial? The question makes me think of Eisenstein integers. Something like, $x^2+xy+y^2 = (x-\omega y)(x-\omega^2y)$, where $\omega = e^{\frac{2\pi i}{3}}$. Then since $\mathbb{Z}[\omega]$ is a UFD with units $\{\pm 1, \pm \omega, \pm \omega^2\}$, there can be at most six solutions to $x^2+xy+y^2 = N$ for any positive integer $N$. So the non-existence of $c$ follows from a basic pigeon hole argument.
26.10.2012 14:22
ocha wrote: ... $x^2+xy+y^2 = (x-\omega y)(x-\omega^2y)$, where $\omega = e^{\frac{2\pi i}{3}}$. Then since $\mathbb{Z}[\omega]$ is a UFD with units $\{\pm 1, \pm \omega, \pm \omega^2\}$, there can be at most six solutions to $x^2+xy+y^2 = N$ for any positive integer $N$. ... I agree with You when $N$ is an Eisenstein prime, but how about in the general case ?
04.11.2012 16:23
Let not leave the things unfinished. Maybe 4) (from my post above) is possible, maybe not, but to finish the problem we need a weaker claim. I should have mentioned at the begining that WLOG we can assume all elements of $A$ are positive. Notice that the same arguments, that lead to claim 3) , also imply the following stronger assertion: 3') Let us fix arbitrary $k \in \mathbb{N}$, then for sufficiently big $n$ there exist $s'_1,s'_2,\ldots, s'_k \in \Gamma'(d);\, s1,s_2,\ldots,s_k \in \Gamma(d)$ such that for every $i,\, 1\leq i \leq k$ $s'_i$ moves in some moments over $s_1,s_2,\ldots, s_k$. 3') implies the following: 4') For each fixed $k$, there exist points $A_1, B_1; A_2,B_2$ and $A'_1, B'_1;A'_2, B'_2;\ldots; A'_k, B'_k$ lying on the curve $y=x^3$ such that: for each $i,\, 1\leq i \leq k \,\Rightarrow \, A_1A'_i \parallel B_1B'_i,A_2A'_i \parallel B_2B'_i $. Now we will prove that 4') is impossible for $k > 2$. Proof. Let $A_j= (a_j, a_j^3),\, B_j=(b_j,b_j^3),\, j=1,2.$ If $A'_i=(x,x^3), B'_i=(y,y^3)$ then $x,y$ satisfy the system: $\begin{cases}\frac{x^3-a_1^3}{x-a_1}= \frac{y^3-b_1^3}{y-b_1} \\ \frac{x^3-a_2^3}{x-a_2}= \frac{y^3-b_2^3}{y-b_2} \end{cases} $ or (*) $\begin{cases} x^2 + a_1 x +a_1^2= y^2+b_1y +b_1^2 \\ x^2 +a_2x+a_2^2= y^2+b_2y+b_2^2\end{cases}$ which yields: $(a_1-a_2)x + a_1^2 - a_2^2 = (b_1-b_2)y + b_1^2- b_2^2 $. Thus some more calculations show us that (*) has at most 2 solutions, therefore (4') is possible only when $k \leq 2$. I am curious to see the official solution.