Greg Kuperberg
Reputation
41,291
149/100 score
 Oct 1 awarded Yearling Sep 14 comment Learning the exponents in a sum of two modular roots of unity Yes, this paper on lens spaces: arxiv.org/abs/1509.02887 Sep 14 awarded Nice Question Aug 28 accepted Learning the exponents in a sum of two modular roots of unity Aug 28 comment Learning the exponents in a sum of two modular roots of unity If you could send me your name by private e-mail, I'd be more than happy to thank you for this, even though you just basically caught me in a mistake. Aug 28 comment Learning the exponents in a sum of two modular roots of unity At least if you fix q, then problem cannot be any easier than discrete logarithm. If you know b, then it simply is the discrete logarithm problem. Aug 28 comment Learning the exponents in a sum of two modular roots of unity Duh, I think you're right, this works. I'm not entirely sure why I missed it, other than that I was moving too quickly. I actually had a different question at first that I simplified to this one with a similar trick. Aug 28 revised Learning the exponents in a sum of two modular roots of unity added 39 characters in body Aug 28 comment Learning the exponents in a sum of two modular roots of unity Think about it. If $q > n^3$, then you expect all $n$ values of $f$ to be distinct. The Weil estimate is generally in the ballpark of heuristic counting. Aug 28 comment Learning the exponents in a sum of two modular roots of unity If $m < q^{1/4}$, then $q$ has at most 4/3 as many digits as $n$. Aug 28 comment Learning the exponents in a sum of two modular roots of unity Thanks, Felipe, but it's actually a zero-dimensional variety rather than a curve because you also have $x^n = y^n = 1$. Aug 28 comment Learning the exponents in a sum of two modular roots of unity I thought of that. Unfortunately, $n^2$ is not coprime to $n$. Aug 28 comment Learning the exponents in a sum of two modular roots of unity I agree that the question is easy if $n$ factors into small prime powers. This is not the difficult end of the question, but it is a useful remark. What if $n$ is prime? Aug 28 comment Learning the exponents in a sum of two modular roots of unity Take the problem this way: $n$ has 100 digits. Every time you call $f$, you are charged one hundredth of one cent for every digit of $q$. You are also charged for electricity for use of your own computer. What do you do? Aug 28 comment Learning the exponents in a sum of two modular roots of unity If you were allowed direct access to $\mathbb{Z}[\zeta_n]$, or even more clearly to $\mathbb{Z}[\mathbb{Z}/n]$, then the problem would be easy. Indeed, $\mathbb{Z}[\zeta_n] \subseteq \mathbb{Z}_p$. But how much $p$-adic precision is necessary for the question? Aug 28 comment Learning the exponents in a sum of two modular roots of unity Okay, it's not obvious why it's impractical. The reason is that $f$ may not be computed directly in the form given; it may just equal the right side. It may have a much more complicated formula that renders calculation in $\mathbb{Z}[\zeta_n]$ impractical. Aug 28 comment Learning the exponents in a sum of two modular roots of unity Yes, that's the point. The crux of the matter is computational complexity. $\mathbb{Z}[\zeta_n]$ is clearly impractical in the terms of this question, hence I consider finite quotients. Aug 28 asked Learning the exponents in a sum of two modular roots of unity Aug 24 awarded Nice Answer Jul 27 awarded Nice Answer