8
$\begingroup$

A nice Lemma due to Konyagin asserts that for any subset $B \subset \mathbb{F}_p$ holds $$ |B.B - B.B + B.B - B.B + B.B - B.B| \geq \frac{1}{2}\min\{p, |B|^2 \}, $$ where the standard notation for the product set $B.B$ is used. Now suppose that instead of $B.B$ we have a partial productset $B\stackrel{G}{.}B$ along the edges of a graph $G$ of edge density $\epsilon$ (meaning that $b_1b_2 \in B\stackrel{G}{.}B$ if only if $b_1, b_2 \in B$ are adjacent in $G$).

Is it true that if $B < \sqrt{p}$ a similar estimate $$ |B\stackrel{G}{.}B + B\stackrel{G}{.}B + B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B| \gg_{\epsilon} |B|^2 $$ holds?

UPD Sorry for sloppy notation. So what it means. $B.B = \{b_ib_j |b_i, b_j \in B \}$, $B.B-B.B = \{b_ib_j - b_kb_l |b_i, b_j, b_k, b_k \in B\}$, and $B.B+B.B$ etc. being defined the same way.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I have a hard time understanding the notation. Can you please clarify it? There are a bunch of B.B's with plus and minus signs that seem to formally cancel. $\endgroup$
    – Lev Borisov
    Aug 23, 2013 at 14:01
  • $\begingroup$ @LevBorisov $B\cdot B=\{ab\mid a,b\in B\}$, $A\pm B=\{a\pm b\mid a\in A,b\in B\}$. Also, writing $3(B\cdot B-B\cdot B)$ runs the risk of being ambiguous: Would this mean the set on the left of the display, or the set $\{3(ab-cd)\mid a,b,c,d\in B\}$? $\endgroup$
    – Andrés E. Caicedo
    Aug 23, 2013 at 14:33
  • 1
    $\begingroup$ @AndresCaicedo Thanks for the comment, I have updated the question to clarify this. $\endgroup$
    – DmitryZ
    Aug 23, 2013 at 15:13
  • $\begingroup$ It's still true by the usual argument (averaging over additive energies) that there exists $\lambda\in\mathbb{F}_p$ such that $|B+_G \lambda\cdot B|\geq\frac 12\min\{|G|,p\}$. After that Glibichuk and Konyagin's argument breaks down pretty badly. It's worth noting that they actually show that either $|(c-d)A+(a-b)A|\geq\frac 12\min\{|A|^2,p\}$ or $|(c-d)A+(a-b+c-d)A|\geq\frac 12\min\{|A|^2,p\}$ where $a,b,c,d$ are some elements of $A$. $\endgroup$
    – Brendan Murphy
    Aug 23, 2013 at 17:02
  • $\begingroup$ Also, Bourgain's version of BSG might be helpful here, but I couldn't make it work straight away (see Bourgain's paper "On the Dimension of Kakeya Sets and Related Maximal Inequalities", or the last exercise in section 6.4 of Tao and Vu's book). $\endgroup$
    – Brendan Murphy
    Aug 23, 2013 at 17:05

1 Answer 1

Reset to default
1
$\begingroup$

This is a sketch of a solution in a certain case.

Let $P$ be the set of pairs $(b,b')$ such that $|N_G(b)\cap N_G(b')|\approx_\epsilon |B|$ up to epsilons. Now let $Q=\{(b-b')/(c-c')\colon (b,b'),(c,c')\in P\}$. We need $\approx_\epsilon |B|^2$ such pairs (off the top of my head I'm not sure if this is possible, but I think it's a standard Cauchy-Schwarz argument).

Consider the special case $Q=\mathbb{F}_p$. Since the number of pairs $(b,b')$ is $\approx |B|^2$, we have $$ |B|^4\approx \sum_{\lambda\in Q}E_+(B,\lambda\cdot B). $$ Hence there is a $\lambda\in Q$ such that $E_+(B,\lambda\cdot B)\lesssim |B|^4/p$.

If $S$ and $T$ are subsets of $B$, then $E_+(S,\lambda\cdot T)\lesssim |B|^4/p$ since we can't get more quadruples by taking subsets. If $\lambda=(b-b')/(c-c')$, let $S$ be the neighborhood of $c-c'$ and let $T$ be the neighborhood of $b-b'$. Then $$ |(c-c')\cdot S+(b-b')\cdot T|=|S+\lambda\cdot T|\geq \frac{|S|^2|T|^2}{E_+(S,\lambda T)}\gtrsim_\epsilon p. $$ Now because $(c,x),(c',y)\in G$ for all $x,y\in S$ (and similarly for $b,b',T$), we have $$ |B\cdot_G B-B\cdot_G B+B\cdot_G B-B\cdot_G B|\geq |cS-c'S+bT-b'T|\gtrsim p. $$

Improve this answer
$\endgroup$
5
  • $\begingroup$ It's a nice adaptation! Unfortunately, in the application I have in mind exactly the opposite case is crucial, i.e. when $|B|$ is small, and so is $B-B/B-B$. $\endgroup$
    – DmitryZ
    Aug 27, 2013 at 6:46
  • $\begingroup$ Thanks! I think you could cover that case by a similar method. I'll add the details to the answer. $\endgroup$
    – Brendan Murphy
    Aug 27, 2013 at 8:08
  • $\begingroup$ It indeed looks promising, but all my previous attempts failed at the point where we need to find to subsets $U$ and $W$ of moderate size, such that $U-U/U-U$ and $W-W/W-W$ are disjoint. The regularity lemma says that if only these sets are $\ll B$ then we can find sufficiently many pairs with large intersection of neigborhoods and we are done, but I didn't find a trick how to guarantee disjointness of the quotient sets (or at least that their intersection is small). $\endgroup$
    – DmitryZ
    Aug 27, 2013 at 11:37
  • 1
    $\begingroup$ Actually, I think there are additional difficulties in this case. Although $Q\not=\mathbb{F}_p$ implies that there exists $\lambda\in Q$ such that $\lambda+1\not\in Q$, what we would need for the typical argument is $\lambda+1\not\in (B-B)/(B-B)$. Still you might be able to overcome this by examining the proof of BSG. I don't have tie to work it out now, however I wrote up an edit with a detailed version of the first case, if you would like it (I stopped once I realized the issue with the second case). $\endgroup$
    – Brendan Murphy
    Aug 27, 2013 at 11:37
  • $\begingroup$ I don't know the regularity lemma so well, but we seem to be talking about a similar issue. Feel free to email me if you like. $\endgroup$
    – Brendan Murphy
    Aug 27, 2013 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.