Bounds on size of subset of additive set that is sum-free

  • MHB
  • Thread starter poissonspot
  • Start date
  • Tags
    Bounds Set
In summary: This notation is used to represent a cyclic shift of the sequence, which Erdos then uses to prove the statement.
  • #1
poissonspot
40
0
Hey, I was reading about this is in "Additive Combinatorics" (Additive Combinatorics (Cambridge Studies in Advanced Mathematics): Terence Tao, Van H. Vu: 9780521136563: Amazon.com: Books) on pg. 4 when I went to the references and found this paper (http://renyi.mta.hu/~p_erdos/1965-02.pdf) which proves the statement starting at the bottom of the 6th page. The proofs look very different, but I feel like the same ideas might be being developed. A couple questions:

In Tao's proof, I'm not sure why $x^{-1}a$ is uniformly distributed in Z_p\{0}

In Erdos's, I am unfamiliar with this notation, "a_r,alpha (mod 1)".

Any suggestions? Thx
 
Physics news on Phys.org
  • #2
!In Tao's proof, the reason why $x^{-1}a$ is uniformly distributed in Z_p\{0} is because of the properties of the inverse map. In particular, if we let $f:Z_p \rightarrow Z_p$ be defined by $f(x) = x^{-1}a$, then for any $y \in Z_p\{0\}$, we have $f^{-1}(y) = yx$, which implies that $f^{-1}$ is bijective, and thus $f$ is also bijective. This means that $f$ is a 1-1 onto map, and hence $x^{-1}a$ must be uniformly distributed over $Z_p\{0\}$.In Erdos's paper, "a_r,alpha (mod 1)" refers to a sequence of points on the unit circle, where $a_r$ is the $r$th point in the sequence and $\alpha$ is an angle. Specifically, the sequence is defined as follows: $a_0 = 0, a_1 = e^{2\pi i \alpha}, a_2 = e^{4\pi i \alpha},...,a_r = e^{2r\pi i \alpha}$.
 

FAQ: Bounds on size of subset of additive set that is sum-free

What is an additive set?

An additive set is a set of numbers in which any two numbers can be added together to obtain another number in the set. For example, the set {1, 3, 5} is an additive set because 1+3=4, 1+5=6, and 3+5=8 are all in the set.

What does it mean for a subset to be sum-free?

A subset is sum-free if no two elements in the subset add up to another element in the subset. For example, in the set {1, 3, 5}, the subset {1, 5} is sum-free because 1+5=6, which is not in the subset.

How do you find the bounds on the size of a sum-free subset?

The bounds on the size of a sum-free subset can be found by using the Erdős-Ginzburg-Ziv theorem, which states that in any additive set of n numbers, there exists a sum-free subset of size at least n/2. This means that the maximum size of a sum-free subset is n/2.

What is the significance of finding the bounds on the size of a sum-free subset?

Finding the bounds on the size of a sum-free subset can have practical applications in areas such as cryptography and error-correction coding. It can also provide insights into the structure of additive sets and help guide further research in this area.

How are these bounds determined?

The bounds on the size of a sum-free subset are determined through the use of mathematical proofs and techniques such as combinatorics and number theory. Researchers use these techniques to analyze the properties of additive sets and derive the bounds on the size of sum-free subsets.

Similar threads

Replies
1
Views
3K
Back
Top