Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userReconstruction Algorithms for Sums of Affine Powers
103
0
0.0
(
0
)
Added by
Ignacio Garcia-Marco
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Authors
Ignacio Garcia-Marco
Ask ChatGPT about the research
No Arabic abstract
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?
rate research
Read More
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.
In this paper we develop techniques that eliminate the need of the Generalized Riemann Hypothesis (GRH) from various (almost all) known results about deterministic polynomial factoring over finite fields. Our main result shows that given a polynomial f(x) of degree n over a finite field k, we can find in deterministic poly(n^{log n},log |k|) time either a nontrivial factor of f(x) or a nontrivial automorphism of k[x]/(f(x)) of order n. This main tool leads to various new GRH-free results, most striking of which are: (1) Given a noncommutative algebra over a finite field, we can find a zero divisor in deterministic subexponential time. (2) Given a positive integer r such that either 8|r or r has at least two distinct odd prime factors. There is a deterministic polynomial time algorithm to find a nontrivial factor of the r-th cyclotomic polynomial over a finite field. In this paper, following the seminal work of Lenstra (1991) on constructing isomorphisms between finite fields, we further generalize classical Galois theory constructs like cyclotomic extensions, Kummer extensions, Teichmuller subgroups, to the case of commutative semisimple algebras with automorphisms. These generalized constructs help eliminate the dependence on GRH.
In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditional deterministic subexponential time polynomial factoring algorithm for finite fields to get an underlying m-scheme. We demonstrate how the properties of m-schemes relate to improvements in the deterministic complexity of factoring polynomials over finite fields assuming the generalized Riemann Hypothesis (GRH). In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n-1) is a smooth number.
We study the problem of recovering a collection of $n$ numbers from the evaluation of $m$ power sums. This yields a system of polynomial equations, which can be underconstrained ($m < n$), square ($m = n$), or overconstrained ($m > n$). Fibers and images of power sum maps are explored in all three regimes, and in settings that range from complex and projective to real and positive. This involves surprising deviations from the Bezout bound, and the recovery of vectors from length measurements by $p$-norms.
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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
