<p>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).</p>

<p>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:</p>

<blockquote>
  <p>For any <span class="math-container">$\epsilon &gt; 0$</span>, there exists <span class="math-container">$c\in\mathbb{N}$</span> such that for all sufficiently large <span class="math-container">$n$</span>, the interval <span class="math-container">$[n, n + n^\epsilon]$</span> contains a square-free integer with no prime factors larger than <span class="math-container">$\log^c(n)$</span></p>
</blockquote>

<p>Details of both of the above are described in Micciancio's paper <a href="https://eccc.weizmann.ac.il/report/2013/115/download/" rel="nofollow noreferrer">Locally Dense Codes</a>.</p>

<p>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 <a href="http://math.utoledo.edu/~codenth/Spring_13/3200/NT-books/Smooth_Numbers-Computational_Number_Theory_and_Beyond-Granville.pdf" rel="nofollow noreferrer">Smooth numbers: computational number theory and beyond</a> mentions that a slight relaxation of the problem (no prime factors larger than <span class="math-container">$n^\epsilon$</span>) 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 <a href="https://www.worldscientific.com/doi/abs/10.1142/S1793042116500196" rel="nofollow noreferrer">this</a>), but I am not an expert, and can't say what the limits of current techniques are.</p>

CC BY-SA 4.0
2020-04-01T19:48:33.513Z
2020-04-02T05:12:44.830Z
2020-04-02T05:12:44.830Z
Mark Schultz-Wu
<p>Are there any applications of analytic number theory in TCS?</p>

CC BY-SA 4.0
2020-04-05T20:19:48.393Z
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
CC BY-SA 4.0
2020-04-06T06:45:51.517Z
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
CC BY-SA 4.0
2020-04-06T16:17:19.143Z
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
<soft-question><big-picture><nt.number-theory><comp-number-theory>
Analytic Number theory in TCS
nocitome
# Analytic Number theory in TCS

(Asked by: username_0 on 2020-04-01)

Are there any applications of analytic number theory in TCS?

**Tags:** soft-question, big-picture, nt.number-theory, comp-number-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2020-04-01. Score: 3

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](https://eccc.weizmann.ac.il/report/2013/115/download/).

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](http://math.utoledo.edu/~codenth/Spring_13/3200/NT-books/Smooth_Numbers-Computational_Number_Theory_and_Beyond-Granville.pdf) 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](https://www.worldscientific.com/doi/abs/10.1142/S1793042116500196)), but I am not an expert, and can't say what the limits of current techniques are.


---

