Skip to main content
MathOverflow

Return to Question

Better notation used
Source Link
DmitryZ
DmitryZ
  • 960
  • 6
  • 17

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 $$ |3B\stackrel{G}{.}B - 3B\stackrel{G}{.}B| \gg_{\epsilon} |B|^2 $$$$ |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$ and so onetc. being defined the same way. $3B.B - 3B.B$ is just a shorthand for $B.B + B.B + B.B - B.B - B.B - B.B$. Analogously, $$ 3B\stackrel{G}{.}B - 3B\stackrel{G}{.}B $$ is simply $$ B\stackrel{G}{.}B + B\stackrel{G}{.}B + B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B, $$ where $B\stackrel{G}{.}B$ denotes the partial productset along the edges of $G$, as explained above.

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 $$ |3B\stackrel{G}{.}B - 3B\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$ and so on being defined the same way. $3B.B - 3B.B$ is just a shorthand for $B.B + B.B + B.B - B.B - B.B - B.B$. Analogously, $$ 3B\stackrel{G}{.}B - 3B\stackrel{G}{.}B $$ is simply $$ B\stackrel{G}{.}B + B\stackrel{G}{.}B + B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B, $$ where $B\stackrel{G}{.}B$ denotes the partial productset along the edges of $G$, as explained above.

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.

added 3 characters in body
Source Link
DmitryZ
DmitryZ
  • 960
  • 6
  • 17

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 $$ |3B\stackrel{G}{.}B - 3B\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}$$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$ and so on being defined analogouslythe same way. $3B.B - 3B.B$ is just a shorthand for $B.B + B.B + B.B - B.B - B.B - B.B$. Analogously, $$ 3B\stackrel{G}{.}B - 3B\stackrel{G}{.}B $$ is simply $$ B\stackrel{G}{.}B + B\stackrel{G}{.}B + B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B, $$ where $B\stackrel{G}{.}B$ denotes the partial productset along the edges of $G$, as explained above.

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 $$ |3B\stackrel{G}{.}B - 3B\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$ and so on being defined analogously. $3B.B - 3B.B$ is just a shorthand for $B.B + B.B + B.B - B.B - B.B - B.B$. Analogously, $$ 3B\stackrel{G}{.}B - 3B\stackrel{G}{.}B $$ is simply $$ B\stackrel{G}{.}B + B\stackrel{G}{.}B + B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B, $$ where $B\stackrel{G}{.}B$ denotes the partial productset along the edges of $G$, as explained above.

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 $$ |3B\stackrel{G}{.}B - 3B\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$ and so on being defined the same way. $3B.B - 3B.B$ is just a shorthand for $B.B + B.B + B.B - B.B - B.B - B.B$. Analogously, $$ 3B\stackrel{G}{.}B - 3B\stackrel{G}{.}B $$ is simply $$ B\stackrel{G}{.}B + B\stackrel{G}{.}B + B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B, $$ where $B\stackrel{G}{.}B$ denotes the partial productset along the edges of $G$, as explained above.

Notation explained in more detail.
Source Link
DmitryZ
DmitryZ
  • 960
  • 6
  • 17

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 $$ |3B\stackrel{G}{.}B - 3B\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$ and so on being defined analogously. $3B.B - 3B.B$ is just a shorthand for $B.B + B.B + B.B - B.B - B.B - B.B$. Analogously, $$ 3B\stackrel{G}{.}B - 3B\stackrel{G}{.}B $$ is simply $$ B\stackrel{G}{.}B + B\stackrel{G}{.}B + B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B, $$ where $B\stackrel{G}{.}B$ denotes the partial productset along the edges of $G$, as explained above.

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 $$ |3B\stackrel{G}{.}B - 3B\stackrel{G}{.}B| \gg_{\epsilon} |B|^2 $$ holds?

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 $$ |3B\stackrel{G}{.}B - 3B\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$ and so on being defined analogously. $3B.B - 3B.B$ is just a shorthand for $B.B + B.B + B.B - B.B - B.B - B.B$. Analogously, $$ 3B\stackrel{G}{.}B - 3B\stackrel{G}{.}B $$ is simply $$ B\stackrel{G}{.}B + B\stackrel{G}{.}B + B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B - B\stackrel{G}{.}B, $$ where $B\stackrel{G}{.}B$ denotes the partial productset along the edges of $G$, as explained above.

Source Link
DmitryZ
DmitryZ
  • 960
  • 6
  • 17