A major topic in additive number theory is the following question: given a set \(A\subseteq \mathbb{N}\), can every sufficiently large positive integer be expressed as the sum of a bounded number of elements of \(A\)? If so, in how many ways can number \(n\) be represented. We say that the set \(A\) is an additive basis of order \(h\) if every positive integer can be written as the sum of at most \(h\) elements from \(A\).
In this chapter of the book I’m reading we prove some really neat inequalities that will be helpful in doing circle method stuff. As you probably know, I kind of self-discovered “the circle method” in some form during my hashing project. I’m moderately hopeful that seeing some of this stuff in more detail / seeing the books take on it will be helpful for hashing. In any case it sounds rather neat.
definitions
Throughout the post we use \(||\alpha||\) to denote the distance from real \(\alpha\) to the nearest integer. We also use \(e(t)\) to denote \(\exp(2\pi i t)\).
some preperatory lemmas
Lemma. \[ \sum_{n=N_1}^{N_2} e(\alpha n) \le \mathcal{O}(N_2-N_1, ||\alpha||^{-1}).\]
Proof. Think about \(e(\alpha n)\) as going around the circle at stride \(||\alpha||^{-1}\). Then this is clear. Ofc if \(||\alpha||^{-1}\) it is sometimes more productive to just say look there are only \(N_2-N_1\) total terms in my sum.
We say \(\alpha\in\mathbb{R}\) is Farey-q-adjacent if \(\alpha\) is distance at most \(1/q^2\) away from some reduced fraction of denominator \(q\).
Lemma. Suppose \(\alpha\) is Farey-q-adjacent. Then \[ \sum_{r=1}^{q/2}\frac{1}{||\alpha r||} \le \mathcal{O}(q\log q). \]
Proof. How to think about this: you got a bunch of points they all be really close to the \(1/q\) fractions. So it makes a lotta sense that we get basically
\[ \sum_{s=1}^{q/2} \frac{}{s/q} \] which is just what we wanted.
Anyways now we be more formal a bit
Ok so the first thing that’s worth being rather worried about is, are we ever dividing by zero?
Luckily you can show that this doesn’t happen. In fact \[ ||\alpha r|| \ge 1/(2q) \] for all \(r\in [q/2]\).
Similar vibes lemma:
Lemma. Suppose \(\alpha\) is Farey-q-adjacent. Then for any integer \(h\) \[ \sum_{r=1}^{q}\min(V, \frac{1}{||\alpha (hq+r)||} \le \mathcal{O}(V+ q\log q). \]
Proof. Same vibes as previous lemma except I guess we might need to take a \(V\) hit \(\mathcal{O}(1)\) times.
Lemma. Let \(\alpha\) be Farey-q-adjacent. Then, \[ \sum_{k=1}^{U} \min(n/k, 1/||\alpha k||) \le \mathcal{O}( (n/q+U+q)(\log 2qU) ). \]
Proof. afaict you just split up the sum and apply the above lemmas
Lemma. Suppose \(\alpha\) is Farey-q-adjacent. Then \[ \sum_{r=1}^{U}\min(n, \frac{1}{||\alpha r||}) \le \mathcal{O}( (q+U+n+\frac{Un}{q})\max(1,\log q)). \]
Proof. Seems like the vibes are just to split up the sum based on values of \(r\) and win.
now we do the important lemmas
Lemma. Let \[S(f) = \sum_{n=N_1}^{N_2} e(f(n)).\] Then \[ |S(f)|^2 = \sum_{|d|<N} \sum_{n\in I(d)} e(\Delta_d(f)(n)) \]
discrete derivative interval.
We also need some version of this for \[ |S(f)|^{2^{\ell}} \] It’s super gross for some reason. looks like they just Cauchy Shwarz the ez version
Theorem. WEYL’s INEQUALITY!
Let \(f(x) = \alpha x^{k}+\cdots\) be a degree \(k\) polynomial. Suppose that \(\alpha\) is Farey-q-adjacent. Let \(S(f) = \sum_{n\in [N]} e(f(n)).\) Let \(K = 2^{k-1}\) and \(\epsilon>0\). Then \[ S(f)\le \mathcal{O}( N^{1+\varepsilon} (N^{-1}+q^{-1}+N^{-k}q)^{1/K} ). \]
weyl differencing
Corollary. For each \(k\ge 2\) there exists \(\delta>0\) such that \(\sqrt{N}\le q \le N^{k-1/2}.\) \[ \sum_{n=1}^{N} e(an^{k}/q) \le \mathcal{O}(N^{1-\delta}) \]
Theorem. Hua’s Lemma
Let \[ T(\alpha) = \sum_{n\in[N]} e(\alpha n^{k}).\] Then \[ \int_0^{1} |T(\alpha)|^{2^{k}} d\alpha \le O(N^{2^{k}-k+\varepsilon}).\]
anyways, it’s kind of hard to see why these are useful until we actually apply it i guess.
Also I didn’t realize but hardy-littlewood or whatever actually have an asymptotic formula for number of ways to write a number as sum of k-th powers. that’s insane.
also note to self should probably just try to go through the theorem with some easy setting like \(k=2\) in mind.