3
$\begingroup$

I have been reading about Additive Combinatorics and in particular Roth's theorem which states any positive upper density set has infinitely many 3-step arithmetic progressions.

Let $A \subset \mathbb{Z}$ be a subset of positive upper density, i.e. $\limsup \tfrac{|A \cap [-N,N]|}{2N+1} > 0$.

Then $A$ contains infinitely many arithmetic progressions $a, a+r, a+2r \in A$.

In fact, I have found numerous expositions on Roth's theorem in recent hears highlighting on technique or another. Fourier analysis, sumset theory, dynamical systems, etc. Here's one of the more peculiar ones:

I am not attacking the merit of these subjects - my colleagues, not mathematicians, do that already. I am enjoying the time I have spent reading about these various techniques, but I want to understand better why there is so much effort in this particular area.

These days I work in industry and every day I see large subsets of $\mathbb{Z}$ in my office, but I am not sure where Additive Combinatorics fits into the picture. Occasionally I have taken an FFT, but I have not computed $A+A$ or anothing, since I am not sure what set $A$ should be.

I am guessing these technical estimates arise in other problems in Number Theory or in the Theoretical CS literature.

In order to make the question focused - and get better answers - I am restricting my attention to Roth's theorem.

Examples could be in a strange places. On a different occasion, I was learning some combinatorial game theory however, in order to implement the algorithms mentioned in that article I had to read about communication complexity lower bound

Improve this question
$\endgroup$
6
  • $\begingroup$ As your question is about the CS literature, maybe it makes more sense to ask it on a CS website? $\endgroup$
    – Gerry Myerson
    Aug 5, 2014 at 3:22
  • 1
    $\begingroup$ @GerryMyerson A candidate would be cstheory.stackexchange.com This question is also about additive combinatorics. I think it goes either way. $\endgroup$
    – john mangual
    Aug 5, 2014 at 12:12
  • 2
    $\begingroup$ It's a very strange question. You know well enough that most subjects in pure mathematics are not developed in view of applications and many do not have at this time (and perhaps will never have) any application. Now it might be possible that the subject of additive combinatorics has some application to CS, and I would understand you asking about tis, but restricting the question to one single theorem in Additive Combinatorics, for no other reason that you have studied this theorem, makes it pointless. Like "what are the applications of Zhang's theorem on bound between primes to biology?" $\endgroup$
    – Joël
    Aug 5, 2014 at 18:38
  • $\begingroup$ @Joël application of twin prime conjecture to computer science would be very interesting $\endgroup$
    – john mangual
    Aug 5, 2014 at 18:42
  • $\begingroup$ Well the term $A+A$ (or to be exact, the difference set $A-A$), is encountered in convolutions (this appears also in the Fourier theoretical approach to arithmetic combinatorics). I agree with you that the "usual" terminology of those arithmetic combinatorics statements are far from being useful in other areas, but other parts of arithmetic combinatorics (say the sum-product theorem) can be stated in a different, more useful, manner (Bourgain's exp. sums estimates pops into mind, or construction of expanders). $\endgroup$
    – Asaf
    Aug 5, 2014 at 21:26

1 Answer 1

Reset to default
5
$\begingroup$

In Testing subgraphs in large graphs Alon established and used a generalization of the classical construction for sets without 3-AP (see Lemma 3.1), so a "lower bound construction" for the quoted problem, to obtain result on the complexity of certain problems in graph theory.

There are various other relations of Additve Combinatorics to CS, and to focus just on Roth's theorem seems not really a good idea. In addition, in this type of mathematics is is often more that the techniques developped can be reused, as opposed to results getting directly applied.

You could start with Additive combinatorics with a view towards computer science and cryptography: An exposition, by Bibak.

Improve this answer
$\endgroup$

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