Polynomial partitioning for several sets of varieties

We give a new, systematic proof for a recent result of Larry Guth and thus also extend the result to a setting with several families of varieties: For any integer \(D\ge 1\) and any collection of sets \(\Gamma _1,\ldots ,\Gamma _j\) of low-degree k-dimensional varieties in \(\mathbb {R}^n\), there exists a non-zero polynomial \(p\in \mathbb {R}[X_1,\ldots ,X_n]\) of degree at most D, so that each connected component of \(\mathbb {R}^n{\setminus }Z(p)\) intersects \(O(jD^{k-n}|\Gamma _i|)\) varieties of \(\Gamma _i\), simultaneously for every \(1\le i\le j\). For \(j=1\), we recover the original result by Guth. Our proof, via an index calculation in equivariant cohomology, shows how the degrees of the polynomials used for partitioning are dictated by the topology, namely, by the Euler class being given in terms of a top Dickson polynomial.     

Generalized Bernstein Operators on the Classical Polynomial Spaces

We study generalizations of the classical Bernstein operators on the polynomial spaces \(\mathbb {P}_{n}[a,b]\), where instead of fixing \(\mathbf {1}\) and x, we reproduce exactly \(\mathbf {1}\) and a polynomial \(f_1\), strictly increasing on [a, b]. We prove that for sufficiently large n, there always exist generalized Bernstein operators fixing \(\mathbf {1}\) and \(f_1\). These operators are defined by non-decreasing sequences of nodes precisely when \(f_1^\prime > 0\) on (a, b), but even if \(f_1^\prime \) vanishes somewhere inside (a, b), they converge to the identity.     

EKR Sets for Large <Emphasis Type="Italic">n</Emphasis> and <Emphasis Type="Italic">r</Emphasis>

Let \(\mathcal {A}\subset \left( {\begin{array}{c}[n]\\ r\end{array}}\right) \) be a compressed, intersecting family and let \(X\subset [n]\). Let \(\mathcal {A}(X)=\{A\in \mathcal {A}:A\cap X\ne \emptyset \}\) and \(\mathcal {S}_{n,r}=\left( {\begin{array}{c}[n]\\ r\end{array}}\right) (\{1\})\). Motivated by the Erd?s–Ko–Rado theorem, Borg asked for which \(X\subset [2,n]\) do we have \(|\mathcal {A}(X)|\le |\mathcal {S}_{n,r}(X)|\) for all compressed, intersecting families \(\mathcal {A}\)? We call X that satisfy this property EKR. Borg classified EKR sets X such that \(|X|\ge r\). Barber classified X, with \(|X|\le r\), such that X is EKR for sufficiently large n, and asked how large n must be. We prove n is sufficiently large when n grows quadratically in r. In the case where \(\mathcal {A}\) has a maximal element, we sharpen this bound to \(n>\varphi ^{2}r\) implies \(|\mathcal {A}(X)|\le |\mathcal {S}_{n,r}(X)|\). We conclude by giving a generating function that speeds up computation of \(|\mathcal {A}(X)|\) in comparison with the naïve methods.     

Counting polynomial subset sums

Let D be a subset of a finite commutative ring R with identity. Let \(f(x)\in R[x]\) be a polynomial of degree d. For a nonnegative integer k, we study the number \(N_f(D,k,b)\) of k-subsets S in D such that

$$\begin{aligned} \sum _{x\in S} f(x)=b. \end{aligned}$$

In this paper, we establish several bounds for the difference between \(N_f(D,k, b)\) and the expected main term \(\frac{1}{|R|}{|D|\atopwithdelims ()k}\), depending on the nature of the finite ring R and f. For \(R=\mathbb {Z}_n\), let \(p=p(n)\) be the smallest prime divisor of n, \(|D|=n-c \ge C_dn p^{-\frac{1}{d}}\,+\,c\) and \(f(x)=a_dx^d +\cdots +a_0\in \mathbb {Z}[x]\) with \((a_d, \ldots , a_1, n)=1\). Then

$$\begin{aligned} \left| N_f(D, k, b)-\frac{1}{n}{n-c \atopwithdelims ()k}\right| \le {\delta (n)(n-c)+(1-\delta (n))\left( C_dnp^{-\frac{1}{d}}+c\right) +k-1\atopwithdelims ()k}, \end{aligned}$$

answering an open question raised by Stanley (Enumerative combinatorics, 1997) in a general setting, where \(\delta (n)=\sum _{i\mid n, \mu (i)=-1}\frac{1}{i}\) and \(C_d=e^{1.85d}\). Furthermore, if n is a prime power, then \(\delta (n) =1/p\) and one can take \(C_d=4.41\). Similar and stronger bounds are given for two more cases. The first one is when \(R=\mathbb {F}_q\), a q-element finite field of characteristic p and f(x) is general. The second one is essentially the well-known subset sum problem over an arbitrary finite abelian group. These bounds extend several previous results.

     

Universal Cycle Packings and Coverings for <Emphasis Type="Italic">k</Emphasis>-Subsets of an <Emphasis Type="Italic">n</Emphasis>-Set

A cyclic sequence of elements of [n] is an (n, k)-Ucycle packing (respectively, (n, k)-Ucycle covering) if every k-subset of [n] appears in this sequence at most once (resp. at least once) as a subsequence of consecutive terms. Let \(p_{n,k}\) be the length of a longest (n, k)-Ucycle packing and \(c_{n,k}\) the length of a shortest (n, k)-Ucycle covering. We show that, for a fixed \(k,p_{n,k}={n\atopwithdelims ()k}-O(n^{\lfloor k/2\rfloor })\). Moreover, when k is not fixed, we prove that if \(k=k(n)\le n^{\alpha }\), where \(0<\alpha <1/3\), then \(p_{n,k}={n\atopwithdelims ()k}-o({n\atopwithdelims ()k}^\beta )\) and \(c_{n,k}={n\atopwithdelims ()k}+o({n\atopwithdelims ()k}^\beta )\), for some \(\beta <1\). Finally, we show that if \(k=o(n)\), then \(p_{n,k}={n\atopwithdelims ()k}(1-o(1))\).     

Monochromatic Solutions for Multi-Term Unknowns

Given integers \(k\ge 2\), \(n \ge 2\), \(m \ge 2\) and \( a_1,a_2,\ldots ,a_m \in {\mathbb {Z}}{\backslash }{\{0\}}\), and let \(f(z)= \sum _{j=0}^{n}c_jz^j\) be a polynomial of integer coefficients with \(c_n>0\) and \((\sum _{i=1}^ma_i)|f(z)\) for some integer z. For a k-coloring of \([N]=\{1,2,\ldots ,N\}\), we say that there is a monochromatic solution of the equation \(a_1x_1+a_2x_2+\cdots +a_mx_m=f(z)\) if there exist pairwise distinct \(x_1,x_2,\ldots ,x_m\in [N]\) all of the same color such that the equation holds for some \(z\in \mathbb {Z}\). Problems of this type are often referred to as Ramsey-type problems. In this paper, it is shown that if \(a_i>0\) for \(1\le i\le m\), then there exists an integer \(N_0=N(k,m,n)\) such that for \(N\ge N_0\), each k-coloring of [N] contains a monochromatic solution \(x_1,x_2,\ldots ,x_m\) of the equation \(a_1x_1+a_2x_2+ \cdots +a_mx_m= f(z)\). Moreover, if n is odd and there are \(a_i\) and \(a_j\) such that \(a_ia_j<0\) for some \(1 \le i\ne j\le m\), then the assertion holds similarly.     

On some permutation binomials and trinomials over $$\mathbb {F}_{2^n}$$

In this work, we completely characterize (1) permutation binomials of the form \(x^{{{2^n -1}\over {2^t-1}}+1}+ ax \in \mathbb {F}_{2^n}[x], n = 2^st, a \in \mathbb {F}_{2^{2t}}^{*}\), and (2) permutation trinomials of the form \(x^{2^s+1}+x^{2^{s-1}+1}+\alpha x \in \mathbb {F}_{2^t}[x]\), where s, t are positive integers. The first result, which was our primary motivation, is a consequence of the second result. The second result may be of independent interest.     

Determination of cusp forms by central values of Rankin–Selberg <Emphasis Type="BoldItalic">L</Emphasis>-functions<Superscript>*</Superscript>

Let f be a fixed holomorphic Hecke eigen cusp form of weight k for \( SL\left( {2,{\mathbb Z}} \right) \), and let \( {\mathcal U} = \left\{ {{u_j}:j \geqslant 1} \right\} \) be an orthonormal basis of Hecke–Maass cusp forms for \( SL\left( {2,{\mathbb Z}} \right) \). We prove an asymptotic formula for the twisted first moment of the Rankin–Selberg L-functions \( L\left( {s,f \otimes {u_j}} \right) \) at \( s = \frac{1}{2} \) as u _j runs over \( {\mathcal U} \). It follows that f is uniquely determined by the central values of the family of Rankin–Selberg L-functions \( \left\{ {L\left( {s,f \otimes {u_j}} \right):{u_j} \in {\mathcal U}} \right\} \).     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

Complete mappings and Carlitz rank

The well-known Chowla and Zassenhaus conjecture, proven by Cohen in 1990, states that for any \(d\ge 2\) and any prime \(p>(d^2-3d+4)^2\) there is no complete mapping polynomial in \(\mathbb {F}_p[x]\) of degree d. For arbitrary finite fields \(\mathbb {F}_q\), we give a similar result in terms of the Carlitz rank of a permutation polynomial rather than its degree. We prove that if \(n<\lfloor q/2\rfloor \), then there is no complete mapping in \(\mathbb {F}_q[x]\) of Carlitz rank n of small linearity. We also determine how far permutation polynomials f of Carlitz rank \(n<\lfloor q/2\rfloor \) are from being complete, by studying value sets of \(f+x.\) We provide examples of complete mappings if \(n=\lfloor q/2\rfloor \), which shows that the above bound cannot be improved in general.     

BTTB preconditioners for BTTB systems

In this paper, we consider solving the BTTB system \({\cal T}_{m,n}[f] {\bf{x}} = {\bf{b}}\) by the preconditioned conjugate gradient (PCG) method, where \({\cal T}_{m,n}[f]\) denotes the m × m block Toeplitz matrix with n × n Toeplitz blocks (BTTB) generated by a (2π, 2π)-periodic continuous function f(x, y). We propose using the BTTB matrix \({\cal T}_{m,n}[1/f]\) to precondition the BTTB system and prove that only O(m)?+?O(n) eigenvalues of the preconditioned matrix \({\cal T}_{m,n}[1/f] {\cal T}_{m,n}[f]\) are not around 1 under the condition that f(x, y)?>?0. We then approximate 1/f(x, y) by a bivariate trigonometric polynomial, which can be obtained in O(m n log(m n)) operations by using the fast Fourier transform technique. Numerical results show that our BTTB preconditioner is more efficient than block circulant preconditioners.     

Detailed error analysis for a fractional Adams method with graded meshes

We consider a fractional Adams method for solving the nonlinear fractional differential equation \(\,^{C}_{0}D^{\alpha }_{t} y(t) = f(t, y(t)), \, \alpha >0\), equipped with the initial conditions \(y^{(k)} (0) = y_{0}^{(k)}, k=0, 1, \dots , \lceil \alpha \rceil -1\). Here, α may be an arbitrary positive number and ?α? denotes the smallest integer no less than α and the differential operator is the Caputo derivative. Under the assumption \(\,^{C}_{0}D^{\alpha }_{t} y \in C^{2}[0, T]\), Diethelm et al. (Numer. Algor. 36, 31–52, 2004) introduced a fractional Adams method with the uniform meshes t _n = T(n/N),n = 0,1,2,…,N and proved that this method has the optimal convergence order uniformly in t _n , that is O(N ^?2) if α > 1 and O(N ^?1?α ) if α ≤ 1. They also showed that if \(\,^{C}_{0}D^{\alpha }_{t} y(t) \notin C^{2}[0, T]\), the optimal convergence order of this method cannot be obtained with the uniform meshes. However, it is well-known that for y ∈ C ^m [0,T] for some \(m \in \mathbb {N}\) and 0 < α < m, the Caputo fractional derivative \(\,^{C}_{0}D^{\alpha }_{t} y(t) \) takes the form “\(\,^{C}_{0}D^{\alpha }_{t} y(t) = c t^{\lceil \alpha \rceil -\alpha } + \text {smoother terms}\)” (Diethelm et al. Numer. Algor. 36, 31–52, 2004), which implies that \(\,^{C}_{0}D^{\alpha }_{t} y \) behaves as t ^?α??α which is not in C ²[0,T]. By using the graded meshes t _n = T(n/N) ^r ,n = 0,1,2,…,N with some suitable r > 1, we show that the optimal convergence order of this method can be recovered uniformly in t _n even if \(\,^{C}_{0}D^{\alpha }_{t} y\) behaves as t ^σ ,0 < σ < 1. Numerical examples are given to show that the numerical results are consistent with the theoretical results.     

Congruences for 7 and 49-regular partitions modulo powers of 7

Let \(b_{k}(n)\) denote the number of k-regular partitions of n. In this paper, we prove Ramanujan-type congruences modulo powers of 7 for \(b_{7}(n)\) and \(b_{49}(n)\). For example, for all \(j\ge 1\) and \(n\ge 0\), we prove that

$$\begin{aligned} b_{7}\Bigg (7^{2j-1}n+\frac{3\cdot 7^{2j-1}-1}{4}\Bigg )\equiv 0\pmod {7^{j}} \end{aligned}$$

and

$$\begin{aligned} b_{49}\Big (7^{j}n+7^{j}-2\Big )\equiv 0\pmod {7^{j}}. \end{aligned}$$

     

On Filtered Polynomial Approximation on the Sphere

This paper considers filtered polynomial approximations on the unit sphere \(\mathbb {S}^d\subset \mathbb {R}^{d+1}\), obtained by truncating smoothly the Fourier series of an integrable function f with the help of a “filter” h, which is a real-valued continuous function on \([0,\infty )\) such that \(h(t)=1\) for \(t\in [0,1]\) and \(h(t)=0\) for \(t\ge 2\). The resulting “filtered polynomial approximation” (a spherical polynomial of degree \(2L-1\)) is then made fully discrete by approximating the inner product integrals by an N-point cubature rule of suitably high polynomial degree of precision, giving an approximation called “filtered hyperinterpolation”. In this paper we require that the filter h and all its derivatives up to \(\lfloor \tfrac{d-1}{2}\rfloor \) are absolutely continuous, while its right and left derivatives of order \(\lfloor \tfrac{d+1}{2}\rfloor \) exist everywhere and are of bounded variation. Under this assumption we show that for a function f in the Sobolev space \(W^s_p(\mathbb {S}^d),\ 1\le p\le \infty \), both approximations are of the optimal order \( L^{-s}\), in the first case for \(s>0\) and in the second fully discrete case for \(s>d/p\), conditions which in both cases cannot be weakened.     

Fractional Differentiability for Solutions of Nonlinear Elliptic Equations

We study nonlinear elliptic equations in divergence form

$$\text {div }{\mathcal A}(x,Du)=\text {div } G.$$

When \({\mathcal A}\) has linear growth in D u, and assuming that \(x\mapsto {\mathcal A}(x,\xi )\) enjoys \(B^{\alpha }_{\frac {n}\alpha , q}\) smoothness, local well-posedness is found in \(B^{\alpha }_{p,q}\) for certain values of \(p\in [2,\frac {n}{\alpha })\) and \(q\in [1,\infty ]\). In the particular case \({\mathcal A}(x,\xi )=A(x)\xi \), G = 0 and \(A\in B^{\alpha }_{\frac {n}\alpha ,q}\), \(1\leq q\leq \infty \), we obtain \(Du\in B^{\alpha }_{p,q}\) for each \(p<\frac {n}\alpha \). Our main tool in the proof is a more general result, that holds also if \({\mathcal A}\) has growth s?1 in D u, 2 ≤ s ≤ n, and asserts local well-posedness in L ^q for each q > s, provided that \(x\mapsto {\mathcal A}(x,\xi )\) satisfies a locally uniform VMO condition.

     

Relative Difference Sets and Hadamard Matrices from Perfect Quaternionic Arrays

Let \(G=\mathbf{C}_{n_1}\times \cdots \times \mathbf{C}_{n_m}\) be an abelian group of order \(n=n_1\dots n_m\), where each \(\mathbf{C}_{n_t}\) is cyclic of order \(n_t\). We present a correspondence between the (4n, 2, 4n, 2n)-relative difference sets in \(G\times Q_8\) relative to the centre \(Z(Q_8)\) and the perfect arrays of size \(n_1\times \dots \times n_m\) over the quaternionic alphabet \(Q_8\cup qQ_8\), where \(q=(1+i+j+k)/2\). In view of this connection, for \(m=2\) we introduce new families of relative difference sets in \(G\times Q_8\), as well as new families of Williamson and Ito Hadamard matrices with G-invariant components.     

Sobolev spaces and approximation by affine spanning systems

We develop conditions on a Sobolev function \(\psi \in W^{m,p}({\mathbb{R}}^d)\) such that if \(\widehat{\psi}(0) = 1\) and ψ satisfies the Strang–Fix conditions to order m ? 1, then a scale averaged approximation formula holds for all \(f \in W^{m,p}({\mathbb{R}}^d)\) :

$ f(x) = \lim_{J \to \infty} \frac{1}{J} \sum_{j=1}^{J} \sum_{k \in {{\mathbb{Z}}}^d} c_{j,k}\psi(a_j x - k) \quad {\rm in} W^{m, p}({{\mathbb{R}}}^d).$

The dilations { a _j } are lacunary, for example a _j =  2 ^j , and the coefficients c _j,k are explicit local averages of f, or even pointwise sampled values, when f has some smoothness. For convergence just in \({W^{m - 1,p}({\mathbb{R}}^d)}\) the scale averaging is unnecessary and one has the simpler formula \(f(x) = \lim_{j \to \infty} \sum_{k \in {\mathbb{Z}}^d} c_{j,k}\psi(a_j x - k)\) . The Strang–Fix rates of approximation are recovered. As a corollary of the scale averaged formula, we deduce new density or “spanning” criteria for the small scale affine system \(\{\psi(a_j x - k) : j > 0, k \in {\mathbb{Z}}^d \}\) in \(W^{m,p}({\mathbb{R}}^d)\) . We also span Sobolev space by derivatives and differences of affine systems, and we raise an open problem: does the Gaussian affine system span Sobolev space?

     

Distance Magic Labeling in Complete 4-partite Graphs

Let G be a complete k-partite simple undirected graph with parts of sizes \(p_1\le p_2\cdots \le p_k\). Let \(P_j=\sum _{i=1}^jp_i\) for \(j=1,\ldots ,k\). It is conjectured that G has distance magic labeling if and only if \(\sum _{i=1}^{P_j} (n-i+1)\ge j{{n+1}\atopwithdelims (){2}}/k\) for all \(j=1,\ldots ,k\). The conjecture is proved for \(k=4\), extending earlier results for \(k=2,3\).     

On the primitive divisors of the recurrent sequence $$u_{n+1}=(4\rm{cos}^2(2\pi/7)-1)\it{u}_{n}-u_{n-\rm{1}}$$ with applications to group theory

Consider the sequence of algebraic integers u_n given by the starting values u₀ = 0, u₁ = 1 and the recurrence \(u_{n+1}=(4\rm{cos}^2(2\pi/7)-1)\it{u}_{n}-u_{n-\rm{1}}\). We prove that for any n ? {1, 2, 3, 5, 8, 12, 18, 28, 30} the n-th term of the sequence has a primitive divisor in \(\mathbb{Z}[2\rm{cos}(2\pi/7)]\). As a consequence we deduce that for any suffciently large n there exists a prime power q such that the group PSL₂(q) can be generated by a pair x, y with \(x^2=y^3=(xy)^7=1\) and the order of the commutator [x, y] is exactly n. The latter result answers in affrmative a question of Holt and Plesken.     

On coherent families of uniformizing elements in some towers of Abelian extensions of local number fields

For a local number field K with the ring of integers \( {\mathcal{O}_K} \), the residue field \( {\mathbb{F}_q} \), and uniformizing π, we consider the Lubin–Tate tower \( {K_\pi } = \bigcap\limits_{n \geqslant 0} {{K_n}} \), where K _n = K(π _n ), f(π0) = 0, and f(π _n +1) = π _n . Here f(X) defines the endomorphism [π] of the Lubin–Tate group. If q ≠ 2, then for any formal power series \( g(X) \in {\mathcal{O}_K}\left[ {\left[ X \right]} \right] \) the following equality holds: \( \sum\limits_{n = 0}^\infty {{\text{SP}}{{{K_n}} \mathord{\left/{\vphantom {{{K_n}} K}} \right.} K}} g\left( {{\pi_n}} \right) = - g(0) \). One has a similar equality in the case q = 2.