Timeline for Efficient Dirichlet approximation (continued fractions?) over a number field
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Dec 12, 2016 at 21:12 | answer | added | O. S. Dawg | timeline score: 1 | |
| Jul 29, 2016 at 12:29 | comment | added | Chris Peikert | Thanks, but I don't think this would work -- it's basically simultaneous Diophantine approximation on the $r_i$, which doesn't give a good enough approximation for what we need. | |
| Jul 29, 2016 at 9:08 | comment | added | grad student | I see. And the naive coordinate-by-coordinate approach is insuffiicent? What I mean is is $(a_1,\dots,a_n)$ is your $\mathbf{Z}$-basis, and $\omega = \sum r_i a_i$ for $r_i \in \mathbb{Q}$, then $r_i \approx p_i / q_i$ for say $q_i \leq B$. Then set $Q$ equal to the least common multiple of the $q_i$, and take $J = Q\mathcal{O}_K$ to be your ideal. Then if you want to find an ideal of smaller norm, you can try factoring $J$. | |
| Jul 27, 2016 at 14:41 | comment | added | Chris Peikert | The norm of $J$ need not be exceptionally small -- e.g., $n^n$ would be fine, and it is easy to find such ideals. The degree of the number field could be in the hundreds or more. | |
| Jul 27, 2016 at 14:11 | comment | added | Noah Stephens-Davidowitz | @gradstudent You're right that for fixed J the problem is just a lattice problem. But, the question here is whether we can do much better than that by choosing J adaptively. For example, in the simple one-dimensional case when the number field is just the rationals, where we just want to approximate some x by a rational p/q number with low-ish denominator q, we can do much much better if we're allowed to choose q dependent on x. | |
| S Jul 23, 2016 at 20:52 | history | bounty ended | CommunityBot | ||
| S Jul 23, 2016 at 20:52 | history | notice removed | CommunityBot | ||
| Jul 20, 2016 at 15:50 | comment | added | grad student | I'm not sure how large degree or discriminant these number fields are for your purposes, but just explicitly finding an ideal $J$ of small norm may be quite hard. I guess it comes down to finding integral elements of small norm in the product-of-conjugates sense. But once you have $J$ in hand, finding a basis for $J^{-1}$ is not too hard? And then it boils down to the usual nearest neighbor lattice problem? | |
| S Jul 15, 2016 at 19:17 | history | bounty started | Chris Peikert | ||
| S Jul 15, 2016 at 19:17 | history | notice added | Chris Peikert | Draw attention | |
| Jul 13, 2016 at 18:58 | history | asked | Chris Peikert | CC BY-SA 3.0 |