Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDerandomization and absolute reconstruction for sums of powers of linear forms
67
0
0.0
(
0
)
Added by
Pascal Koiran
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the decomposition of multivariate polynomials as sums of powers of linear forms. As one of our main results we give an algorithm for the following problem: given a homogeneous polynomial of degree 3, decide whether it can be written as a sum of cubes of linearly independent linear forms with complex coefficients. Compared to previous algorithms for the same problem, the two main novel features of this algorithm are: (i) It is an algebraic algorithm, i.e., it performs only arithmetic operations and equality tests on the coefficients of the input polynomial. In particular, it does not make any appeal to polynomial factorization. (ii) For an input polynomial with rational coefficients, the algorithm runs in polynomial time when implemented in the bit model of computation. The algorithm relies on methods from linear and multilinear algebra (symmetric tensor decomposition by simultaneous diagonalization). We also give a version of our algorithm for decomposition over the field of real numbers. In this case, the algorithm performs arithmetic operations and comparisons on the input coefficients. Finally we give several related derandomization results on black box polynomial identity testing, the minimization of the number of variables in a polynomial, the computation of Lie algebras and factorization into products of linear forms.
rate research
Read More
In this paper we study sums of powers of affine functions in (mostly) one variable. Although quite simple, this model is a generalization of two well-studied models: Waring decomposition and sparsest shift. For these three models there are natural extensions to several variables, but this paper is mostly focused on univariate polynomials. We present structural results which compare the expressive power of the three models; and we propose algorithms that find the smallest decomposition of f in the first model (sums of affine powers) for an input polynomial f given in dense representation. We also begin a study of the multivariate case. This work could be extended in several directions. In particular, just as for Sparsest Shift and Waring decomposition, one could consider extensions to supersparse polynomials and attempt a fuller study of the multi-variate case. We also point out that the basic univariate problem studied in the present paper is far from completely solved: our algorithms all rely on some assumptions for the exponents in an optimal decomposition, and some algorithms also rely on a distinctness assumption for the shifts. It would be very interesting to weaken these assumptions, or even to remove them entirely. Another related and poorly understood issue is that of the bit size of the constants appearing in an optimal decomposition: is it always polynomially related to the bit size of the input polynomial given in dense representation?
This paper is devoted to the factorization of multivariate polynomials into products of linear forms, a problem which has applications to differential algebra, to the resolution of systems of polynomial equations and to Waring decomposition (i.e., decomposition in sums of d-th powers of linear forms; this problem is also known as symmetric tensor decomposition). We provide three black box algorithms for this problem. Our main contribution is an algorithm motivated by the application to Waring decomposition. This algorithm reduces the corresponding factorization problem to simultaenous matrix diagonalization, a standard task in linear algebra. The algorithm relies on ideas from invariant theory, and more specifically on Lie algebras. Our second algorithm reconstructs a factorization from several bi-variate projections. Our third algorithm reconstructs it from the determination of the zero set of the input polynomial, which is a union of hyperplanes.
In [9], Migliore, Miro-Roig and Nagel, proved that if $R = mathbb{K}[x,y,z]$, where $mathbb{K}$ is a field of characteristic zero, and $I=(L_1^{a_1},dots,L_r^{a_4})$ is an ideal generated by powers of 4 general linear forms, then the multiplication by the square $L^2$ of a general linear form $L$ induces an homomorphism of maximal rank in any graded component of $R/I$. More recently, Migliore and Miro-Roig proved in [8] that the same is true for any number of general linear forms, as long the powers are uniform. In addition, they conjecture that the same holds for arbitrary powers. In this paper we will solve this conjecture and we will prove that if $I=(L_1^{a_1},dots,L_r^{a_r})$ is an ideal of $R$ generated by arbitrary powers of any set of general linear forms, then the multiplication by the square $L^2$ of a general linear form $L$ induces an homomorphism of maximal rank in any graded component of $R/I$.
We show that the diophantine equation $n^ell+(n+1)^ell + ...+ (n+k)^ell=(n+k+1)^ell+ ...+ (n+2k)^ell$ has no solutions in positive integers $k,n ge 1$ for all $ell ge 3$.
In the past two decades, many researchers have studied {it index $2$} Gauss sums, where the group generated by the characteristic $p$ of the underling finite field is of index $2$ in the unit group of ${mathbb Z}/m{mathbb Z}$ for the order $m$ of the multiplicative character involved. A complete solution to the problem of evaluating index $2$ Gauss sums was given by Yang and Xia~(2010). In particular, it is known that some nonzero integral powers of the Gauss sums in this case are in quadratic fields. On the other hand, Chowla~(1962), McEliece~(1974), Evans~(1977, 1981) and Aoki~(1997, 2004, 2012) studied {it pure} Gauss sums, some nonzero integral powers of which are in the field of rational numbers. In this paper, we study Gauss sums, some integral powers of which are in quadratic fields. This class of Gauss sums is a generalization of index $2$ Gauss sums and an extension of pure Gauss sums to quadratic fields.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
