3
$\begingroup$

Recall that two cyclotomic integers are called associated if their ratio is a unit in the corresponding ring of cyclotomic integers.

We will view cyclotomic integers as polynomials (of degree $<\varphi(n)$) with integer coefficients modulo the cyclotomic polynomial $\Phi_n(x)$.

Q: Given a cyclotomic integer $p(x)$ modulo $\Phi_n(x)$, how to find all its associated cyclotomic integers $q(x)$ that have bounded coefficients?

Particularly interesting cases:

  • $q(x)$ has coefficients from $\{0,1\}$;

  • $q(x)$ has nonnegative coefficients summing to a given integer $s$.

Remark. A naive approach would be generating all polynomials $r(x)$ with bounded integer coefficients of degree at most $\varphi(n)-1$ (there is a finite number of them) and checking if $r(x)/p(x)$ is a unit, however it's hardly feasible for large $n$. I hope it's possible to somehow exploit the structure of units to recover the required polynomials $q(x)$ more efficiently.

Improve this question
$\endgroup$
12
  • $\begingroup$ As a side comment, the units are not easy to find/check: see this question. Also, you could try a simplified search by multiplying for the cyclotomic units which are quite explicit: planetmath.org/…. One could hope to find a bound on which cyclotomic units could possibly contribute (maybe some coefficient diverges when you multiply many times?). But then there is the problem of non-cyclotomic units, which implies a finite search from any candidate polynomial. $\endgroup$
    – Andrea Marino
    Aug 27, 2022 at 22:07
  • 1
    $\begingroup$ Wouldn't it be better to bound the unit, say u, and compute all the u(x)p(x)? Using that the units form a f.g. group under multiplication will give a smaller search space. $\endgroup$
    – Felipe Voloch
    Aug 27, 2022 at 22:07
  • $\begingroup$ @AndreaMarino: As for checking for a unit, isn't it enough to check that the norm equals 1? $\endgroup$
    – Max Alekseyev
    Aug 27, 2022 at 22:19
  • $\begingroup$ @FelipeVoloch: The question here - how exactly to bound suitable units $u(x)$? $\endgroup$
    – Max Alekseyev
    Aug 27, 2022 at 22:20
  • 1
    $\begingroup$ If $q=up$, then $u=q/p$ in the cyclotomic field. The height satisfies $H(ab)\le H(a)H(b), H(1/a)=H(a)$ (Lang, Fund. Dioph Geom 3.1), so $H(u) \le H(q)H(1/p)=H(q)H(p)$. $\endgroup$
    – Felipe Voloch
    Sep 5, 2022 at 3:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.