We give a strict generalization of the LLL algorithm over number fields, based on the reduction theory of $\GL(n)$ over the adele ring of a number field. Our algorithm is free of heuristics, with rigorous bounds on output quality and complexity. As a consequence, we obtain a hierarchy of reductions from module-(H)SVP to ideal-HSVP, an example of which has runtime and approximation factors subexponential in the field degree. More importantly, we uncover a close connection between structured lattice reduction and a Diophantine approximation over number fields.
We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the $\ell_2$ norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field tha...
In the theory of hyperplane arrangements, the study of logarithmic derivation modules is one of the most important subjects. If the module is free over a graded ring, the multiset of degrees of its homogeneous basis is called exponents. We utilize some basic theory of linear algebra to study the exponents of multiarran...
We investigate the approximation of elements of the middle-third Cantor set by dyadic rationals, and natural extensions. We prove a conjecture of Velani, completing the metric theory for the Cantor measure. Our key method enables a quantitative study of the incommensurability of binary and ternary expansions of integer...
We study the complexity of two fundamental problems attached to p-adic lattices: computing an N-orthogonal basis, and deciding whether a given basis is N-orthogonal. When the norm is supplied through an explicit diagonal representation, both problems are polynomial. However, in the black-box model, where the ultrametri...
Pierre Fromonot, Mercedes Haiech, Tristan Vaccon· 0 citations
Let $G$ be a finite group and $x \in G$. In 2013, Hai-Reuven proved that the cardinality of the centralizer of $x$ divides the cardinality of the solubilizer of $x$. Settling a conjecture of Mousavi, Poozesh and Zamani, we show that the cardinality of the normalizer of $\langle x \rangle$ is also a divisor. We actually...
Luca Sabatini· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
