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
    Commented 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
    Commented Aug 23, 2013 at 14:33
  • 1
    $\begingroup$ @AndresCaicedo Thanks for the comment, I have updated the question to clarify this. $\endgroup$
    – DmitryZ
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Aug 27, 2013 at 11:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .