Skip to main content
added some more info
Source Link
Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24

Bounding size of partial difference sets given size of partial sumsets

In this paper by Katz and Tao, the following bounds were established.

Let $A,B$ be finite subsets of an abelian group, with $|A|,|B|\le N$. We fix some $G \subset A\times B$. We define $C = \{a+b:(a,b) \in G\},D=\{a+2b:(a,b)\in G\}, X = \{a-b:(a,b)\in G\}$.

  1. If $|C|\le N$, then $|X| \le N^{2-1/6}$, and it is possible for $|X| \ge N^{\log(6)/\log(3)} = N^{2-0.369\dots}$ to hold.
  2. If $|C|\le N,|D|\le N$, then $|X| \le N^{2-1/4}$, and it is possible for $|X| \ge N^{2-1/2}$ to hold.

I understand these problems were originally studied to better understand Besicovitch sets and Kakeya's conjecture. I am aware of the paper of Dvir which basically settles Kakeya's conjecture for finite fields, but to my understanding, this would not say anything about what can be deduced of $|X|$.

I find this problem of bounding $|X|$ given $|C|$ and $|D|$ to be quite interesting in its own right, so has this problem been studied further? If so, what are the best known bounds?

Update: I looked at this survey by Katz and Tao which was written shortly after the aforementioned paper. On page 8 of the survey, they talk about this problem of understanding partial sumsets and partial difference sets. They say:

There is a substantial literature on the relative sizes of sum-sets $A_0 + A_1$ and difference sets $A_0 − A_1$ (see e.g. the excellent survey [17]), but much less is known about partial sum-sets and difference sets, when one only considers a subset $G$ of pairs $A_0 \times A_1$.

It has been 20 years since this survey. Can anyone comment to whether the area of partial sumsets has been studied more since then? If not, I'd be interested to hear some speculation to why this is the case.

Bounding size of difference sets given size of sumsets

In this paper, the following bounds were established.

Let $A,B$ be finite subsets of an abelian group, with $|A|,|B|\le N$. We fix some $G \subset A\times B$. We define $C = \{a+b:(a,b) \in G\},D=\{a+2b:(a,b)\in G\}, X = \{a-b:(a,b)\in G\}$.

  1. If $|C|\le N$, then $|X| \le N^{2-1/6}$, and it is possible for $|X| \ge N^{\log(6)/\log(3)} = N^{2-0.369\dots}$ to hold.
  2. If $|C|\le N,|D|\le N$, then $|X| \le N^{2-1/4}$, and it is possible for $|X| \ge N^{2-1/2}$ to hold.

I understand these problems were originally studied to better understand Besicovitch sets and Kakeya's conjecture. I am aware of the paper of Dvir which basically settles Kakeya's conjecture for finite fields, but to my understanding, this would not say anything about what can be deduced of $|X|$.

I find this problem of bounding $|X|$ given $|C|$ and $|D|$ to be quite interesting in its own right, so has this problem been studied further? If so, what are the best known bounds?

Bounding size of partial difference sets given size of partial sumsets

In this paper by Katz and Tao, the following bounds were established.

Let $A,B$ be finite subsets of an abelian group, with $|A|,|B|\le N$. We fix some $G \subset A\times B$. We define $C = \{a+b:(a,b) \in G\},D=\{a+2b:(a,b)\in G\}, X = \{a-b:(a,b)\in G\}$.

  1. If $|C|\le N$, then $|X| \le N^{2-1/6}$, and it is possible for $|X| \ge N^{\log(6)/\log(3)} = N^{2-0.369\dots}$ to hold.
  2. If $|C|\le N,|D|\le N$, then $|X| \le N^{2-1/4}$, and it is possible for $|X| \ge N^{2-1/2}$ to hold.

I understand these problems were originally studied to better understand Besicovitch sets and Kakeya's conjecture. I am aware of the paper of Dvir which basically settles Kakeya's conjecture for finite fields, but to my understanding, this would not say anything about what can be deduced of $|X|$.

I find this problem of bounding $|X|$ given $|C|$ and $|D|$ to be quite interesting in its own right, so has this problem been studied further? If so, what are the best known bounds?

Update: I looked at this survey by Katz and Tao which was written shortly after the aforementioned paper. On page 8 of the survey, they talk about this problem of understanding partial sumsets and partial difference sets. They say:

There is a substantial literature on the relative sizes of sum-sets $A_0 + A_1$ and difference sets $A_0 − A_1$ (see e.g. the excellent survey [17]), but much less is known about partial sum-sets and difference sets, when one only considers a subset $G$ of pairs $A_0 \times A_1$.

It has been 20 years since this survey. Can anyone comment to whether the area of partial sumsets has been studied more since then? If not, I'd be interested to hear some speculation to why this is the case.

Source Link
Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24

Bounding size of difference sets given size of sumsets

In this paper, the following bounds were established.

Let $A,B$ be finite subsets of an abelian group, with $|A|,|B|\le N$. We fix some $G \subset A\times B$. We define $C = \{a+b:(a,b) \in G\},D=\{a+2b:(a,b)\in G\}, X = \{a-b:(a,b)\in G\}$.

  1. If $|C|\le N$, then $|X| \le N^{2-1/6}$, and it is possible for $|X| \ge N^{\log(6)/\log(3)} = N^{2-0.369\dots}$ to hold.
  2. If $|C|\le N,|D|\le N$, then $|X| \le N^{2-1/4}$, and it is possible for $|X| \ge N^{2-1/2}$ to hold.

I understand these problems were originally studied to better understand Besicovitch sets and Kakeya's conjecture. I am aware of the paper of Dvir which basically settles Kakeya's conjecture for finite fields, but to my understanding, this would not say anything about what can be deduced of $|X|$.

I find this problem of bounding $|X|$ given $|C|$ and $|D|$ to be quite interesting in its own right, so has this problem been studied further? If so, what are the best known bounds?