41,096 reputation
4140227
bio website math.ucdavis.edu/~greg
location Davis, CA
age 48
visits member for 5 years, 11 months
seen 10 hours ago
I am a professor at UC Davis.


1d
accepted Learning the exponents in a sum of two modular roots of unity
1d
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.
1d
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.
1d
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.
1d
revised Learning the exponents in a sum of two modular roots of unity
added 39 characters in body
1d
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.
1d
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$.
1d
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$.
1d
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$.
1d
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?
1d
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?
1d
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?
1d
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.
1d
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.
1d
asked Learning the exponents in a sum of two modular roots of unity
Aug
24
awarded  Nice Answer
Jul
27
awarded  Nice Answer
Jul
16
awarded  Good Answer
Jun
1
awarded  Nice Answer
May
27
awarded  Good Answer