Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals

This paper studies the representation of a positive polynomial f(x) on a noncompact semialgebraic set S={x∈Rⁿ:g₁(x)≥0,…,g_s(x)≥0} modulo its KKT (Karush-Kuhn-Tucker) ideal. Under the assumption that the minimum value of f(x) on S is attained at some KKT point, we show that f(x) can be represented as sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)>0 on S; furthermore, when the KKT ideal is radical, we argue that f(x) can be represented as a sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)≥0 on S. This is a generalization of results in [J. Nie, J. Demmel, B. Sturmfels, Minimizing polynomials via sum of squares over the gradient ideal, Mathematical Programming (in press)], which discusses the SOS representations of nonnegative polynomials over gradient ideals.     

Newton Polygons of L Functions Associated with Exponential Sums of Polynomials of Degree Four over Finite Fields

Let F_q be the finite field of q elements with characteristic p and F_q^m its extension of degree m. Fix a nontrivial additive character Ψ of F_p. If f(x₁,…, x_n)∈F_q[x₁,…, x_n] is a polynomial, then one forms the exponential sum S_m(f)=∑_{(x1,…,xn)∈(Fq^m)ⁿ}Ψ(Tr_Fq^m/Fp(f(x₁,…,x_n))). The corresponding L functions are defined by L(f, t)=exp(∑^∞_m=0S_m(f)t^m/m). In this paper, we apply Dwork's method to determine the Newton polygon for the L function L(f(x), t) associated with one variable polynomial f(x) when deg f(x)=4. As an application, we also give an affirmative answer to Wan's conjecture for the case deg f(x)=4.     

Incomplete Character Sums and Polynomial Interpolation of the Discrete Logarithm

In the first part of the paper, certain incomplete character sums over a finite field F_p^r are considered which in the case of finite prime fields F_p are of the form ∑^A+N−1_n=Aχ(g(n))ψ(f(n)), where A and N are integers with 1≤N<p, g and f are polynomials over F_p, and χ denotes a multiplicative and ψ an additive character of F_p. Excluding trivial cases, it is shown that the above sums are at most of the order of magnitude N^1/2p^r/4. Recently, Shparlinski showed that a polynomial f over the integers which coincides with the discrete logarithm of the finite prime field F_p for N consecutive elements of F_p must have a degree at least of the order of magnitude Np^−1/2. In this paper this result is extended to arbitrary F_p^r. The proof is based on the above new bound for incomplete hybrid character sums.     

On the Evaluation of Weil Sums of Dembowski-Ostrom Polynomials

Let F_q denote the finite field of q elements, q=p^e odd, let χ₁ denote the canonical additive character of F_q where χ₁(c)=e^2πiTr(c)/p for all c∈F_q, and let Tr represent the trace function from F_q to F_p. We are interested in evaluating Weil sums of the form S=S(a₁, …, a_n)=∑_x∈Fq χ₁(D(x)) where D(x)=∑ⁿ_i=1 a_ix^pα_i+pβ_i, α_i?β_i for each i, is known as a Dembowski-Ostrom polynomial (or as a D-O polynomial). Coulter has determined the value of S when D(x)=ax^pα+1; in this note we show how Coulter's methods can be generalized to determine the absolute value of S for any D-O polynomial. When e is even, we give a subclass of D-O polynomials whose Weil sums are real-valued, and in certain cases we are able to resolve the sign of S. We conclude by showing how Coulter's work for the monomial case can be used to determine a lower bound on the number of F^l_q-solutions to the diagonal-type equation ∑^l_i=1 x^pγ+1_i+(x_i+λ)^pγ+1=0, where l is even, e/gcd(γ, e) is odd, and h (X)=λ^pe−γX^pe−γ+λ^pγX is a permutation polynomial over F_q.     

On the Behaviour of the spectral characteristic of Feigenbaum’s map

Let T _g : [?1, 1] ?? [?1, 1] be the Feigenbaum map. It is well known that T _g has a Cantor-type attractor F and a unique invariant measure ??₀ supported on F. The corresponding unitary operator (U _g ??)(x) = ??(g(x)) has pure point spectrum consisting of eigenvalues ?? _n,r , n ?? 1, 0 ?? r ?? 2 ^n?1 ? 1 with eigenfunctions e _r ⁽ⁿ⁾ (x). Suppose that f ?? C ¹([?1, 1]), f?? is absolutely continuous on [?1, 1] and f?? ?? L ^p ([?1, 1], d??₀), p > 1. Consider the sum of the amplitudes of the spectral measure of f: $$ Sn(f): = \sum\limits_{r = 0}^{2^n - 1} {|\rho _r^{(n)} |^2 ,\rho _r^{(n)} = \int\limits_{ - 1}^1 {f(x)\overline {e_r^{(n)} (x)} d\mu _o } } (x). $$ Using the thermodynamic formalism for T _g we prove that S _n (f) ?? 2^?n q ⁿ , as n ?? ??, where the constant q ?? (0, 1) does not depend on f.     

Weak solution of (r, (x, u(x)) u′(x))′ = (Fu)′(x) with r(0, u(0))u′(0) = ku(0), r(L, u(L))u′ (L) = hu(L) and k, h are suitable elements of [0, ∞]

We consider weak solutions to the nonlinear boundary value problem (r, (x, u(x)) u′(x))′ = (Fu)′(x) with r(0, u(0)) u′(0) = ku(0), r(L, u(L)) u′(L) = hu(L) and k, h are suitable elements of [0, ∞]. In addition to studying some new boundary conditions, we also relax the constraints on r(x, u) and (Fu)(x). r(x, u) > 0 may have a countable set of jump discontinuities in u and r(x, u)^?1?L_q((0, L) × (0, p)). F is an operator from a suitable set of functions to a subset of L_p(0, L) which have nonnegative values. F includes, among others, examples of the form (Fu)(x) = (1 ? H(x ? x₀)) u(x₀), (Fu)(x) = ∫_x^Lf(y, u(y)) dy where f(y, u) may have a countable set of jump discontinuities in u or F may be chosen so that (Fu)′(x) = ? g(x, u(x)) u′(x) ? q(x) u(x) ? f(x, u(x)) where q is a distributional derivative of an L₂(0, L) function.     

Max-min of polynomials and exponential diophantine equations

In this paper we study the maximum-minimum value of polynomials over the integer ring Z. In particular, we prove the following: Let F(x,y) be a polynomial over Z. Then, maxx∈Z(T)miny∈Z|F(x,y)|=o(T1/2) as T→∞ if and only if there is a positive integer B such that maxx∈Zminy∈Z|F(x,y)|?B. We then apply these results to exponential diophantine equations and obtain that: Let f(x,y), g(x,y) and G(x,y) be polynomials over Q, G(x,y)∈(Q[x,y]−Q[x])∪Q, and b a positive integer. For every α in Z, there is a y in Z such that f(α,y)+g(α,y)bG(α,y)=0 if and only if for every integer α there exists an h(x)∈Q[x] such that f(x,h(x))+g(x,h(x))bG(x,h(x))≡0, and h(α)∈Z.     

On subword decomposition and balanced polynomials

Let H(x) be a monic polynomial over a finite field F=GF(q). Denote by Na(n) the number of coefficients in Hn which are equal to an element a∈F, and by G the set of elements a∈F^× such that Na(n)>0 for some n. We study the relationship between the numbers (Na(n))_a∈G and the patterns in the base q representation of n. This enables us to prove that for “most” n's we have Na(n)≈Nb(n), a,b∈G. Considering the case H=x+1, we provide new results on Pascal's triangle modulo a prime. We also provide analogous results for the triangle of Stirling numbers of the first kind.     

On the number of zero-sum subsequences

For a sequence S of elements from an additive abelian group G, let f(S) denote the number of subsequences of S the sum of whose terms is zero. In this paper we characterize all sequences S in G with f(S)>2^|S|-2, where |S| denotes the number of terms of S.     

Lower bound of overall exponential sums for polynomialsϕ(x d )

LetS ⁽¹⁾ (n, Q) denote the maximum module of exponential sums for polynomials of degree n over the Galois fieldF _Q . In a previous paper the transition to the multiple exponential sums allowed us to obtain a good lower bound of the valueS ⁽¹⁾ (n, Q), which coincides with Weil's bound whenn = q ^(m-1)/2 + 1, whereq, m are odd andm 3. Here the same approach is used for the estimation of the valueS ^(d) (n, Q), which corresponds to polynomials(x ^d ) overF _Q , whered is any divisor ofq – 1.     

Two linear equations in formal power series

The equations [gradφ(x)]^TF(x)=h(x) and F(ψ(x))–ψ(x) are considered. They arise in the stability theory of differential and difference equations. The scalar function h(x) is a given, and the function ψ(x) an unknown, formal power series in the n indeterminates x=(x₁,…,x_n)^T, and h(0)=ψ=0; the elements of the n×n matrix F(x) are also formal power series in x, F(0)=0. It is shown that the solvability of both equations depends on the eigenvalues of the Jacobian F_x(0).     

Normality criteria of meromorphic functions with multiple zeros

Take positive integers n,k?2. Let F be a family of meromorphic functions in a domain D⊂C such that each f∈F has only zeros of multiplicity at least k. If, for each pair (f,g) in F, fn(f(k)) and gn(g(k)) share a non-zero complex number a ignoring multiplicity, then F is normal in D.     

On R-robustly entropy-expansive diffeomorphisms

For a homoclinic class H(p _f ) of f ?? Diff¹(M), f?OH(p _f ) is called R-robustly entropy-expansive if for g in a locally residual subset around f, the set ?? _? (x) = {y ?? M: dist(g ⁿ (x), g ⁿ (y)) ?? g3 (?n ?? ?)} has zero topological entropy for each x ?? H(p _g ). We prove that there exists an open and dense set around f such that for every g in it, H(p _g ) admits a dominated splitting of the form E ?? F ₁ ?? ... ?? F _k ?? G where all of F _i are one-dimensional and non-hyperbolic, which extends a result of Pacifico and Vieitez for robustly entropy-expansive diffeomorphisms. Some relevant consequences are also shown.     

Properties of convergence for the q-Meyer-König and Zeller operators

In this paper, we discuss properties of convergence for the q-Meyer-König and Zeller operators Mn,q. Based on an explicit expression for Mn,q(t²,x) in terms of q-hypergeometric series, we show that for qn∈(0,1], the sequence (Mn,qn(f))_n?1 converges to f uniformly on [0,1] for each f∈C[0,1] if and only if limn→∞qn=1. For fixed q∈(0,1), we prove that the sequence (Mn,q(f)) converges for each f∈C[0,1] and obtain the estimates for the rate of convergence of (Mn,q(f)) by the modulus of continuity of f, and the estimates are sharp in the sense of order for Lipschitz continuous functions. We also give explicit formulas of Voronovskaya type for the q-Meyer-König and Zeller operators for fixed 0<q<1. If 0<q<1, f∈C¹[0,1], we show that the rate of convergence for the Meyer-König and Zeller operators is o(qn) if and only if

     

Nonsingularity of matrices associated with classes of arithmetical functions on lcm-closed sets

Let S = {x₁, … , x_n} be a set of n distinct positive integers and f be an arithmetical function. Let [f(x_i, x_j)] denote the n × n matrix having f evaluated at the greatest common divisor (x_i, x_j) of x_i and x_j as its i, j-entry and (f[x_i, x_j]) denote the n × n matrix having f evaluated at the least common multiple [x_i, x_j] of x_i and x_j as its i, j-entry. The set S is said to be lcm-closed if [x_i, x_j] ∈ S for all 1 ? i, j ? n. For an integer x > 1, let ω(x) denote the number of distinct prime factors of x. Define ω(1) = 0. In this paper, we show that if S = {x₁, … , x_n} is an lcm-closed set satisfying , and if f is a strictly increasing (resp. decreasing) completely multiplicative function, or if f is a strictly decreasing (resp. increasing) completely multiplicative function satisfying (resp. f(p) ? p) for any prime p, then the matrix [f(x_i, x_j)] (resp. (f[x_i, x_j])) defined on S is nonsingular. By using the concept of least-type multiple introduced in [S. Hong, J. Algebra 281 (2004) 1-14], we also obtain reduced formulas for det(f(x_i, x_j)) and det(f[x_i, x_j]) when f is completely multiplicative and S is lcm-closed. We also establish several results about the nonsingularity of LCM matrices and reciprocal GCD matrices.     

Solving polynomial optimization problems via the truncated tangency variety and sums of squares

Let f,g_i,i=1,…,l,h_j,j=1,…,m, be polynomials on Rⁿ and S?{x∈Rⁿ∣g_i(x)=0,i=1,…,l,h_j(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S.     

Finite determinacy and Whitney equisingularity of map germs from {\mathbb{C}^n} to {\mathbb{C}^{2n-1}}

We show that a holomorphic map germ ${f : (\mathbb{C}^n,0)\to(\mathbb{C}^{2n-1},0)}$ is finitely determined if and only if the double point scheme D(f) is a reduced curve. If n ≥ 3, we have that μ(D ²(f)) = 2μ(D ²(f)/S ₂)+C(f)?1, where D ²(f) is the lifting of the double point curve in ${(\mathbb{C}^n\times \mathbb{C}^n,0)}$ , μ(X) denotes the Milnor number of X and C(f) is the number of cross-caps that appear in a stable deformation of f. Moreover, we consider an unfolding F(t, x) = (t, f _t (x)) of f and show that if F is μ-constant, then it is excellent in the sense of Gaffney. Finally, we find a minimal set of invariants whose constancy in the family f _t is equivalent to the Whitney equisingularity of F. We also give an example of an unfolding which is topologically trivial, but it is not Whitney equisingular.     

A new result on Davenport constant

Let G be a finite abelian group of order n and Davenport constant D(G). Let S=⁰h(S)_∏g∈Ggvg(S)∈F(G) be a sequence with a maximal multiplicity h(S) attained by 0 and t=|S|?n+D(G)−1. Then 0∈k_∑(S) for every 1?k?t+1−D(G). This is a refinement of the fundamental result of Gao [W.D. Gao, A combinatorial problem on finite abelian groups, J. Number Theory 58 (1996) 100-103].     

On the irreducibility of a class of polynomials,III

This work is a continuation and extension of our earlier articles on irreducible polynomials. We investigate the irreducibility of polynomials of the form g(f(x)) over an arbitrary but fixed totally real algebraic number field $\text{L}$, where g(x) and f(x) are monic polynomials with integer coefficients in $\text{L}$, g is irreducible over $\text{L}$ and its splitting field is a totally imaginary quadratic extension of a totally real number field. A consequence of our main result is as follows. If g is fixed then, apart from certain exceptions f of bounded degree, g(f(x)) is irreducible over $\text{L}$ for all f having distinct roots in a given totally real number field.     

On additive polynomials and certain maximal curves

We show that a maximal curve over F_q² given by an equation A(X)=F(Y), where A(X)∈F_q²[X] is additive and separable and where F(Y)∈F_q²[Y] has degree m prime to the characteristic p, is such that all roots of A(X) belong to F_q². In the particular case where F(Y)=Y^m, we show that the degree m is a divisor of q+1.