Polynomials with bounds and numerical approximation

We discuss the generation of polynomials with two bounds —an upper bound and a lower bound— on compact sets \(\mathcal C=[0,1]^{d}\subset \mathbb {R}^{d}\) in view on numerical approximation and scientific computing. The presentation is restricted to d = 1,2. We show that a composition formula based on a weighted 4-squares Euler identity generates all such polynomials in dimension d=1. It yields a new algebraic or compositional approach to the classical problem related to polynomials with minimal uniform norm. The theoretical generalization to the multivariate case is discussed in dimension d=2 by means of the 8-squares Degen identity and the connection with quaternions algebras is made explicit. Numerical results in dimension d=1 illustrate the potentialities of this approach and some implementation details are provided.     

A characterization of the normal distribution using stationary max-stable processes

Consider a max-stable process of the form \(\eta (t) = \max _{i\in \mathbb {N}} U_{i} \mathrm {e}^{\langle X_{i}, t\rangle - \kappa (t)}\), \(t\in \mathbb {R}^{d}\), where \(\{U_{i}, i\in \mathbb {N}\}\) are points of the Poisson process with intensity u ^?2du on (0,∞), X _i , \(i\in \mathbb {N}\), are independent copies of a random d-variate vector X (that are independent of the Poisson process), and \(\kappa :\mathbb {R}^{d} \to \mathbb {R}\) is a function. We show that the process η is stationary if and only if X has multivariate normal distribution and κ(t)?κ(0) is the cumulant generating function of X. In this case, η is a max-stable process introduced by R. L. Smith.     

On the number of monic integer polynomials with given signature

In this paper, we show that the number of monic integer polynomials of degree \(d \ge 1\) and height at most H which have no real roots is between \(c_1H^{d-1/2}\) and \(c_2 H^{d-1/2}\), where the constants \(c_2>c_1>0\) depend only on d. (Of course, this situation may only occur for d even.) Furthermore, for each integer s satisfying \(0 \le s < d/2\) we show that the number of monic integer polynomials of degree d and height at most H which have precisely 2s non-real roots is asymptotic to \(\lambda (d,s)H^{d}\) as \(H \rightarrow \infty \). The constants \(\lambda (d,s)\) are all positive and come from a recent paper of Bertók, Hajdu, and Peth?. They considered a similar question for general (not necessarily monic) integer polynomials and posed this as an open question.     

On EA-equivalence of certain permutations to power mappings

In this paper we investigate the existence of permutation polynomials of the form x ^d  + L(x) on \({{\mathbb{F}_{2^n}}}\) , where \({{L(x)\in\mathbb{F}_{2^n}[x]}}\) is a linearized polynomial. It is shown that for some special d with gcd(d, 2 ⁿ ?1) > 1, x ^d  + L(x) is nerve a permutation on \({{\mathbb{F}_{2^n}}}\) for any linearized polynomial \({{L(x)\in\mathbb{F}_{2^n}[x]}}\) . For the Gold functions \({{x^{2^i+1}}}\) , it is shown that \({{x^{2^i+1}+L(x)}}\) is a permutation on \({{\mathbb{F}_{2^n}}}\) if and only if n is odd and \({{L(x)=\alpha^{2^i}x+\alpha x^{2^i}}}\) for some \({{\alpha\in\mathbb{F}_{2^n}^{*}}}\) . We also disprove a conjecture in (Macchetti Addendum to on the generalized linear equivalence of functions over finite fields. Cryptology ePrint Archive, Report2004/347, 2004) in a very simple way. At last some interesting results concerning permutation polynomials of the form x ^?1 + L(x) are given.     

Compactly Supported,Piecewise Polyharmonic Radial Functions with Prescribed Regularity

A compactly supported radially symmetric function \(\varPhi :\Bbb{R}^{d}\to \Bbb{R}\) is said to have Sobolev regularity k if there exist constants B≥A>0 such that the Fourier transform of Φ satisfies

$A\bigl(1+\Vert\omega\Vert ^2\bigr)^{-k} \leq\widehat{\varPhi }(\omega )\leq B\bigl (1+\Vert\omega\Vert ^2\bigr)^{-k},\quad\omega\in \Bbb{R}^d.$

Such functions are useful in radial basis function methods because the resulting native space will correspond to the Sobolev space \(W_{2}^{k}(\Bbb{R}^{d})\). For even dimensions d and integers k≥d/4, we construct piecewise polyharmonic radial functions with Sobolev regularity k. Two families are actually constructed. In the first, the functions have k nontrivial pieces, while in the second, exactly one nontrivial piece. We also explain, in terms of regularity, the effect of restricting Φ to a lower dimensional space \(\Bbb{R}^{d-2\ell}\) of the same parity.

     

A note on Hamiltonicity of uniform random intersection graphs

We consider a collection of n independent random subsets of [m] = {1, 2, . . . , m} that are uniformly distributed in the class of subsets of size d, and call any two subsets adjacent whenever they intersect. This adjacency relation defines a graph called the uniform random intersection graph and denoted by G _n,m,d . We fix d = 2, 3, . . . and study when, as n,m → ∞, the graph G _n,m,d contains a Hamilton cycle (the event denoted \( {G_{n,m,d}} \in \mathcal{H} \)). We show that \( {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = o(1) \) for d ² nm ^?1 ? lnm ? 2 ln lnm → ?∞ and \( {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = 1 - o(1) \) for 2nm ^?1 ? lnm ? ln lnm → +∞.     

Abelian Cayley Graphs of Given Degree and Diameter 2 and 3

Let CC _d,k be the largest possible number of vertices in a cyclic Cayley graph of degree d and diameter k, and let AC _d,k be the largest order in an Abelian Cayley graph for given d and k. We show that \({CC_{d,2} \geq \frac{13}{36} (d + 2)(d -4)}\) for any d= 6p?2 where p is a prime such that \({p \neq 13}\) , \({p \not\equiv 1}\) (mod 13), and \({AC_{d,3} \geq \frac{9}{128} (d + 3)^2(d - 5)}\) for d = 8q?3 where q is a prime power.     

Weighted fractional Bernstein’s inequalities and their applications

This paper studies the weighted, fractional Bernstein inequality for spherical polynomials on S^d-1\(\left( {0.1} \right)\;{\left\| {{{\left( { - {\Delta _0}} \right)}^{{\raise0.7ex\hbox{$r$} \!\mathord{\left/ {\vphantom {r 2}}\right.\kern-\nulldelimiterspace}\!\lower0.7ex\hbox{$2$}}}}f} \right\|_{p,w}} \leqslant {C_w}{n^r}{\left\| f \right\|_{p,w}}\;for\;all\;f \in \Pi _n^d\), where Π_n^d denotes the space of all spherical polynomials of degree at most n on S^d-1 and (-Δ₀)^r/2 is the fractional Laplacian-Beltrami operator on S^d-1. A new class of doubling weights with conditions weaker than the A_p condition is introduced and used to characterize completely those doubling weights w on S^d-1 for which the weighted Bernstein inequality (0.1) holds for some 1 ≤ p ≤ 8 and all r > t. It is shown that in the unweighted case, if 0 < p < 8 and r > 0 is not an even integer, (0.1) with w = 1 holds if and only if r > (d - 1)((1/p) - 1). As applications, we show that every function f ∈ L_p(S^d-1) with 0 < p < 1 can be approximated by the de la Vallée Poussin means of a Fourier-Laplace series and establish a sharp Sobolev type embedding theorem for the weighted Besov spaces with respect to general doubling weights.     

On vanishing coefficients of algebraic power series over fields of positive characteristic

Let K be a field of characteristic p>0 and let f(t ₁,…,t _d ) be a power series in d variables with coefficients in K that is algebraic over the field of multivariate rational functions K(t ₁,…,t _d ). We prove a generalization of both Derksen’s recent analogue of the Skolem–Mahler–Lech theorem in positive characteristic and a classical theorem of Christol, by showing that the set of indices (n ₁,…,n _d )∈? ^d for which the coefficient of \(t_{1}^{n_{1}}\cdots t_{d}^{n_{d}}\) in f(t ₁,…,t _d ) is zero is a p-automatic set. Applying this result to multivariate rational functions leads to interesting effective results concerning some Diophantine equations related to S-unit equations and more generally to the Mordell–Lang Theorem over fields of positive characteristic.     

Representations of the general linear group over symmetry classes of polynomials

Let V be the complex vector space of homogeneous linear polynomials in the variables x₁,..., x _m . Suppose G is a subgroup of S _m , and χ is an irreducible character of G. Let H _d (G, χ) be the symmetry class of polynomials of degree d with respect to G and χ.

For any linear operator T acting on V, there is a (unique) induced operator K _χ (T) ∈ End(H _d (G, χ)) acting on symmetrized decomposable polynomials by

$${K_\chi }\left( T \right)\left( {{f_1} * {f_2} * \cdots * {f_d}} \right) = T{f_1} * T{f_2} * \cdots * T{f_d}.$$

In this paper, we show that the representation T ? K _χ (T) of the general linear group GL(V) is equivalent to the direct sum of χ(1) copies of a representation (not necessarily irreducible) T ? B _χ ^G (T).

     

Refined Bounds on the Number of Connected Components of Sign Conditions on a Variety

Let \({\textnormal {R}}\) be a real closed field, \(\mathcal{P},\mathcal{Q} \subset {\textnormal {R}}[X_{1},\ldots,X_{k}]\) finite subsets of polynomials, with the degrees of the polynomials in \(\mathcal{P}\) (resp., \(\mathcal{Q}\)) bounded by d (resp., d ₀). Let \(V \subset {\textnormal {R}}^{k}\) be the real algebraic variety defined by the polynomials in \(\mathcal{Q}\) and suppose that the real dimension of V is bounded by k′. We prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of the family \(\mathcal{P}\) on V is bounded by

$\sum_{j=0}^{k'}4^j{s +1\choose j}F_{d,d_0,k,k'}(j),$

where \(s = \operatorname {card}\mathcal{P}\), and

$F_{d,d_0,k,k'}(j)=\binom{k+1}{k-k'+j+1} (2d_0)^{k-k'}d^j \max\{2d_0,d \}^{k'-j}+2(k-j+1).$

In case 2d ₀≤d, the above bound can be written simply as

$\sum_{j = 0}^{k'} {s+1 \choose j}d^{k'} d_0^{k-k'} O(1)^{k}= (sd)^{k'} d_0^{k-k'} O(1)^k$

(in this form the bound was suggested by Matousek 2011). Our result improves in certain cases (when d ₀?d) the best known bound of

$\sum_{1 \leq j \leq k'}\binom{s}{j} 4^{j} d(2d-1)^{k-1}$

on the same number proved in Basu et al. (Proc. Am. Math. Soc. 133(4):965–974, 2005) in the case d=d ₀.

The distinction between the bound d ₀ on the degrees of the polynomials defining the variety V and the bound d on the degrees of the polynomials in \(\mathcal{P}\) that appears in the new bound is motivated by several applications in discrete geometry (Guth and Katz in arXiv:1011.4105v1 [math.CO], 2011; Kaplan et al. in arXiv:1107.1077v1 [math.CO], 2011; Solymosi and Tao in arXiv:1103.2926v2 [math.CO], 2011; Zahl in arXiv:1104.4987v3 [math.CO], 2011).     

Dependence of Hilbert coefficients

Let M be a finitely generated module of dimension d and depth t over a Noetherian local ring (A, \({\mathfrak{m}}\)) and I an \({\mathfrak{m}}\)-primary ideal. In the main result it is shown that the last t Hilbert coefficients \({e_{d-t+1}(I,M),\ldots, e_{d}(I,M)}\) are bounded below and above in terms of the first d ? t + 1 Hilbert coefficients \({e_{0}(I,M),\ldots,e_{d-t}(I,M)}\) and d.     

Sharp Weak Type Inequalities for Fractional Integral Operators

Suppose that d≥1 is an integer, α∈(0,d) is a fixed parameter and let I _α be the fractional integral operator associated with d-dimensional Walsh-Fourier series on (0,1] ^d . Let p, q be arbitrary numbers satisfying the conditions 1≤p<d/α and 1/q=1/p?α/d. We determine the optimal constant K, which depends on α, d and p, such that for any f∈L ^p ((0,1] ^d ) we have

$$ ||I_{\alpha } f||_{L^{q,\infty }((0,1]^{d})}\leq K||f||_{L^{p}((0,1]^{d})}. $$

In fact, we shall prove this inequality in the more general context of probability spaces equipped with a regular tree-like structures. This allows us to obtain this result also for non-integer dimension. The proof exploits a certain modification of the so-called Bellman function method and appropriate interpolation-type arguments. We also present a sharp weighted weak-type bound for I _α , which can be regarded as a version of the Muckenhoupt-Wheeden conjecture for fractional integral operators.

     

On the exceptional sets in Sylvester expansions*

For any x ?? (0, 1], let the series \( {\sum}_{n=1}^{\infty }1/{d}_n(x) \) be the Sylvester expansion of x, where {d _j (x),?j?≥?1} is a sequence of positive integers satisfying d₁(x)?≥?2 and d_j?+?1(x)?≥?d _j (x)(d _j (x)???1)?+?1 for j?≥?1. Suppose ? : ? → ?⁺ is a function satisfying ?(n+1) – ? (n) → ∞ as n → ∞. In this paper, we consider the set

$$ E\left(\phi \right)=\left\{x\kern0.5em \in \left(0,1\right]:\kern0.5em \underset{n\to \infty }{\lim}\frac{\log {d}_n(x)-{\sum}_{j=1}^{n-1}\log {d}_j(x)}{\phi (n)}=1\right\} $$

and quantify the size of the set in the sense of Hausdorff dimension. As applications, for any β > 1 and γ > 0, we get the Hausdorff dimension of the set \( \left\{x\in \kern1em \left(0,1\right]:\kern0.5em {\lim}_{n\to \infty}\left(\log {d}_n(x)-{\sum}_{j=1}^{n-1}\log {d}_j(x)\right)/{n}^{\beta }=\upgamma \right\}, \) and for any τ > 1 and η > 0, we get a lower bound of the Hausdorff dimension of the set \( \left\{x\kern0.5em \in \kern0.5em \left(0,1\right]:\kern1em {\lim}_{n\to \infty}\left(\log {d}_n(x)-{\sum}_{j=1}^{n-1}\log {d}_j(x)\right)/{\tau}^n=\eta \right\}. \)     

Entropy and Widths of Multiplier Operators on Two-Point Homogeneous Spaces

In this article we continue the development of methods of estimating n-widths and entropy of multiplier operators begun in 1992 by A. Kushpel (Fourier Series and Their Applications, pp. 49–53, 1992; Ukr. Math. J. 45(1):59–65, 1993). Our main aim is to give an unified treatment for a wide range of multiplier operators Λ on symmetric manifolds. Namely, we investigate entropy numbers and n-widths of decaying multiplier sequences of real numbers \(\varLambda=\{\lambda_{k}\}_{k=1}^{\infty}\), |λ ₁|≥|λ ₂|≥?, \(\varLambda:L_{p}(\mathbb{M}^{d}) \rightarrow L_{q}(\mathbb{M}^{d})\) on two-point homogeneous spaces \(\mathbb{M}^{d}\): \(\mathbb{S}^{d}\), ? ^d (?), ? ^d (?), ? ^d (?), ?¹⁶(Cay). In the first part of this article, general upper and lower bounds are established for entropy and n-widths of multiplier operators. In the second part, different applications of these results are presented. In particular, we show that these estimates are order sharp in various important situations. For example, sharp order estimates are found for function sets with finite and infinite smoothness. We show that in the case of finite smoothness (i.e., |λ _k |?k ^?γ (lnk)^?ζ, γ/d>1, ζ≥0, k→∞), we have \(e_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d})) \ll d_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d}))\), n→∞, but in the case of infinite smoothness (i.e., \(|\lambda_{k}| \asymp e^{-\gamma k^{r}}\), γ>0, 0<r≤1, k→∞), we have \(e_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d})) \gg d_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d}))\), n→∞ for different p and q, where \(U_{p}(\mathbb{S}^{d})\) denotes the closed unit ball of \(L_{p}(\mathbb{S}^{d})\).     

Permutations of finite fields for check digit systems

Let q be a prime power. For a divisor n of q ? 1 we prove an asymptotic formula for the number of polynomials of the form

$f(X)=\frac{a-b}{n}\left(\sum_{j=1}^{n-1}X^{j(q-1)/n}\right)X+\frac{a+b(n-1)}{n}X\in\mathbb{F}_q[X]$

such that the five (not necessarily different) polynomials f(X), f(X)±X and f(f(X))±X are all permutation polynomials over \({\mathbb{F}_q}\) . Such polynomials can be used to define check digit systems that detect the most frequent errors: single errors, adjacent transpositions, jump transpositions, twin errors and jump twin errors.

     

Improved bounds on the Hadwiger–Debrunner numbers

Let HD _d (p, q) denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in Rd which satisfy the (p, q)-property (p ≥ q ≥ d + 1). In a celebrated proof of the Hadwiger–Debrunner conjecture, Alon and Kleitman proved that HD _d (p, q) exists for all p ≥ q ≥ d + 1. Specifically, they prove that \(H{D_d}(p,d + 1)is\tilde O({p^{{d^2} + d}})\).We present several improved bounds: (i) For any \(q \geqslant d + 1,H{D_d}(p,d) = \tilde O({p^{d(\frac{{q - 1}}{{q - d}})}})\). (ii) For q ≥ log p, \(H{D_d}(p,q) = \tilde O(p + {(p/q)^d})\). (iii) For every ? > 0 there exists a p₀ = p₀(?) such that for every p ≥ p₀ and for every \(q \geqslant {p^{\frac{{d - 1}}{d} + \in }}\) we have p ? q + 1 ≤ HD _d (p, q) ≤ p ? q + 2. The latter is the first near tight estimate of HD _d (p, q) for an extended range of values of (p, q) since the 1957 Hadwiger–Debrunner theorem.We also prove a (p, 2)-theorem for families in R² with union complexity below a specific quadratic bound.     

A discrete version of Koldobsky’s slicing inequality

Let #K be a number of integer lattice points contained in a set K. In this paper we prove that for each d ∈ N there exists a constant C(d) depending on d only, such that for any origin-symmetric convex body K ? R ^d containing d linearly independent lattice points

$$\# K \leqslant C\left( d \right)\max \left( {\# \left( {K \cap H} \right)} \right)vo{l_d}{\left( K \right)^{\frac{{d - m}}{d}}},$$

where the maximum is taken over all m-dimensional subspaces of R ^d . We also prove that C(d) can be chosen asymptotically of order O(1) ^d d ^d?m . In particular, we have order O(1) ^d for hyperplane slices. Additionally, we show that if K is an unconditional convex body then C(d) can be chosen asymptotically of order O(d) ^d?m .

     

Polynomial Properties on Large Symmetric Association Schemes

In this paper we characterize “large” regular graphs using certain entries in the projection matrices onto the eigenspaces of the graph. As a corollary of this result, we show that “large” association schemes become P-polynomial association schemes. Our results are summarized as follows. Let G = (V, E) be a connected k-regular graph with d +1 distinct eigenvalues \({k = \theta_{0} > \theta_{1} > \cdots > \theta_{d}}\). Since the diameter of G is at most d, we have the Moore bound

$$|V| \leq M(k,d) = 1 + k \sum^{d-1}_{i=0} (k-1)^{i}.$$

Note that if |V| > M(k, d ? 1) holds, the diameter of G is equal to d. Let E _i be the orthogonal projection matrix onto the eigenspace corresponding to θ _i . Let ?(u, v) be the path distance of u, v ∈V.

Theorem. Assume \({|V| > M(k, d - 1)}\) holds. Then for x, y ∈V with \({\partial (x, y) = d}\), the (x, y) -entry of E _i is equal to

$$-\frac{1}{|V|} \prod _{j=1,2,...,d, j \neq i} \frac{\theta_{0}-\theta_{j}}{\theta_{i}-\theta_{j}}.$$

If a symmetric association scheme \({\mathfrak{X} = (X, \{R_{i}\}^{d}_{i=0})}\) has a relation R _i such that the graph (X, R _i ) satisfies the above condition, then \({\mathfrak{X}}\) is P-polynomial. Moreover we show the “dual” version of this theorem for spherical sets and Q-polynomial association schemes.