Polynomials that Vanish on Distinct n th Roots of Unity

From MaRDI portal
Polynomials that Vanish on Distinct $n$ th Roots of Unity





Let \(\mathbb C\) denote the field of complex numbers and, for \(0\leq t\leq n-1\), \(J(n,t+1)\subset \mathbb C[x_0,\dots,x_t]\) the ideal of those polynomials in \(x_0,\dots,x_t\) that vanish on \((t+1)\) tuples of distinct \(n\)th roots of unity. Define \(f_0=x_0^n-1\) and for \(1\leq k\leq t\) the polynomial \(f_k=\sum_{a_0+\dots+a_k=n-k}{x_0^{a_0}\cdot\ldots\cdot x_k^{a_k}}\) (i.e., the full symmetric polynomial in \(x_0,\dots,x_k\) of degree \(n-k\)). Then \(G=\{f_0,f_1,\dots,f_t\}\) is a Gröbner basis for \(J(n,t+1)\) and the lexicographic term order with \(x_0<\dots<x_t\). The proof given in the appendix uses the characterization \(f\in J(n,t+1)\iff f\,V\in \langle x_0^n-1,\dots,x_t^n-1\rangle\) where \(V=\prod_{1\leq i<j\leq t}{(x_i-x_j)}\) is the Vandermonde polynomial. As main result the authors prove a combinatorial Nullstellensatz for such ideals, i.e., a characterization of polynomials \(f=\sum_\alpha{c_\alpha x^\alpha}\in \mathbb C[x_0,\dots,x_t]\) with \(f\not\in J(n,t+1)\) in terms of their coefficients: To each monomial \(x^\alpha=x_0^{\alpha_0}\ldots x_t^{\alpha_t}\) associate a function \(\pi_\alpha: \mathbb Z_n\rightarrow \mathbb Z_n\) defined by \(\pi_\alpha(i)\equiv i+\alpha_i\pmod{n}\) and define \(\Lambda=\Lambda_{t+1}= \{\alpha\in \mathbb Z_{\geq 0}^{t+1} : \pi_\alpha\) is a permutation of \(\{0,1,\dots,t\}\}\). Then \(f\not\in J(n,t+1)\) if and only if there exists some reduced with respect to \(G\) monomial \(x^\beta\) (i.e., \(\beta_i<n-i\) for all \(i=0,\dots,t\)) such that \(c=\sum_{\alpha+\beta\in\Lambda} {c_\alpha\,\text{ sgn}(\pi_{\alpha+\beta})}\neq 0\). Note that \(c\) is actually NF\((x^\beta f,G)(0,\dots,0)\) where NF is the normal form operator with respect to \(G\). The proof uses the stronger result that the matrix \(M(n,t+1)=\| m_{\beta\beta'}\| \) is invertible where \(m_{\beta\beta'}= \text{NF}(x^\beta x^{\beta'},G)(0,\dots,0)\) and \(x^\beta, x^{\beta'}\) run over all monomials reduced with respect to \(G\). As applications, four problems are sketched that can be reduced to membership questions of polynomials in \(J(n,t+1)\) for certain \(n,t\): the description of the coefficient variety of permutation polynomials, i.e., (univariate) polynomials \(g(x)=\sum_{i=0}^{n-1}{\rho_ix^i}\) that permute the \(n\)th roots of unity; perfect matchings in bipartite graphs; Latin transversals in Latin squares of odd order; Hamiltonian cycles in graphs.











This page was built for publication: Polynomials that Vanish on Distinct $n$ th Roots of Unity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4812339)