# Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?

• 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. – Mahdi Cheraghchi Apr 5 '20 at 20:19
• 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. – nocitome Apr 6 '20 at 6:45
• 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. – Mahdi Cheraghchi Apr 6 '20 at 16:17

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)$$
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.