1
$\begingroup$

Are there any applications of analytic number theory in TCS?

$\endgroup$
3
  • $\begingroup$ This is actually a fascinating question, one that I have wondered about for a long time. I'm not sure why it's closed, could be a good community wiki question... Other than the one current answer, I can think of Algebraic Geometry codes that are built on top of lots of tools that in turn use analytic number theory (such as Weil conjectures), or explicit construction of Ramanujan graphs built using the Ramanujan conjecture. But nothing substantial I'm aware of that directly uses the ANT techniques, rather than taking a result from the area as a black box. Voting to reopen. $\endgroup$ – Mahdi Cheraghchi Apr 5 '20 at 20:19
  • $\begingroup$ I know that Laplace's method and saddle point method are sometimes used in combinatorics and probability (for example analytic combinatorics). But I'm not aware of any other applications of techniques from ANT in TCS. $\endgroup$ – nocitome Apr 6 '20 at 6:45
  • $\begingroup$ Modular forms (not exactly ANT but a central tool there) have also recently been applied to lattice packing problems (optimality of Leech and E_8), which are related to the first answer below. $\endgroup$ – Mahdi Cheraghchi Apr 6 '20 at 16:17
3
$\begingroup$

Codes/Lattices are certain combinatorial objects that are commonly used within TCS. A basic question for both of them is finding "short" codewords/lattice points, known as the Minimum Distance problem/Shortest Vector problem (MDP/SVP).

Both have been known to be NP-hard under randomized reductions for 20+ years. Roughly 10 years ago, the NP hardness proof for MDP was derandomized using some Analytic Number Theory (Weil's Character Sum bound). SVP has still not been derandomized, but can be derandomized if the following result in analytic number theory is proven:

For any $\epsilon > 0$, there exists $c\in\mathbb{N}$ such that for all sufficiently large $n$, the interval $[n, n + n^\epsilon]$ contains a square-free integer with no prime factors larger than $\log^c(n)$

Details of both of the above are described in Micciancio's paper Locally Dense Codes.

It's worth mentioning that this "existence of smooth numbers in short intervals" question is known within analytic number theory. For example, section 1.2 of Smooth numbers: computational number theory and beyond mentions that a slight relaxation of the problem (no prime factors larger than $n^\epsilon$) implies Vinogradov's conjecture, a problem in analytic number theory with no progress in 40 years. There are definitely recent publications on this problem (say this), but I am not an expert, and can't say what the limits of current techniques are.

$\endgroup$

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