1

Exercise 2.8.6 from Tao and Vu's Additive Combinatorics asks: Given a subset $A\subset\mathbb{F}_p$ with size $|A|>p^\frac{1}{k}$ $(k\geq 2)$, show $\frac{A-A}{A-A}$ has size at least $p^\frac{1}{k-1}$. It gives the hint that the lower bound on $|A|$ guarantees that for $x_1,\ldots,x_k\in\mathbb{F}_p$ the map $(a_1,\ldots,a_k)\mapsto x_1a_1+\ldots+x_ka_k$ is not injective.

When $k=2$ the proof is fairly simple: Since $|A+xA|\leq p<|A|^2$ there must be a collision $a_1+xa_2=a_1'+xa_2'$ which forces $x\in\frac{A-A}{A-A}$.

I do not know how to prove this theorem (perhaps someone can shed some light on it for me). What I'm more interested in is the following question. What is the minimum number of representations of $x\in\frac{A-A}{A-A}$ as $x=\frac{a-b}{c-d}$.

1 Answers1

0

Here's how to solve the exercise. Assume the contrary, that $|\frac{A-A}{A-A}|<p^\frac{1}{k-1}$. First pick $x_1\notin \frac{A-A}{A-A}$. Then the sums $a_0+x_1a_1$ are distinct. Now pick $x_2 \notin\frac{A-A}{A-A}+x_1\cdot\frac{A-A}{A-A}$. Then the sums $a_0+x_1a_1+x_2a_2$ are distinct. Next choose $x_3\notin \frac{A-A}{A-A}+x_1\cdot\frac{A-A}{A-A} +x_2\frac{A_A}{A-A}$. Continue on in this fashion until $x_{k-1}$ has been chosen. Once it has, we will have that $|A+x_1A+\ldots+x_{k-1}A|=|A|^k>p$ which is a contradiction.

brando
  • 31