bio  website  math.ucdavis.edu/~greg 

location  Davis, CA  
age  48  
visits  member for  5 years, 11 months 
seen  10 hours ago  
stats  profile views  26,118 
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 email, 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 zerodimensional 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 