Sums of fractions modulo p

Let \({\mathbb{F}_p}\) be the field of residue classes modulo a large prime p. The present paper is devoted to the problem of representability of elements of \({\mathbb{F}_p}\) as sums of fractions of the form x/y with x, y from short intervals of \({\mathbb{F}_p}\).     

On congruence lattices of nilsemigroups

Cayley hash functions are based on a simple idea of using a pair of (semi)group elements, A and B, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with \(2 \times 2\) matrices over \(\mathbb {F}_p\). Since there are many known pairs of \(2 \times 2\) matrices over \(\mathbb {Z}\) that generate a free monoid, this yields numerous pairs of matrices over \(\mathbb {F}_p\), for a sufficiently large prime p, that are candidates for collision-resistant hashing. However, this trick has a flip side, and lifting matrix entries to \(\mathbb {Z}\) may facilitate finding a collision. This “lifting attack” was successfully used by Tillich and Zémor in the special case where two matrices A and B generate (as a monoid) the whole monoid \(SL_2(\mathbb {Z}_+)\). However, in this paper we show that the situation with other, “similar”, pairs of matrices from \(SL_2(\mathbb {Z})\) is different, and the “lifting attack” can (in some cases) produce collisions in the group generated by A and B, but not in the positive monoid. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from \(SL_2(\mathbb {F}_p)\).     

Algebraic conditions for additive functions over the reals and over finite fields

Let C be an affine plane curve. We consider additive functions \(f{:}\; K\rightarrow K\) for which \(f(x)f(y)=0\), whenever \((x,y)\in C\). We show that if \(K=\mathbb {R}\) and C is the hyperbola with defining equation \(xy=1\), then there exist nonzero additive functions with this property. Moreover, we show that such a nonzero f exists for a field K if and only if K is transcendental over \(\mathbb Q\) or over \(\mathbb {F}_p\), the finite field with p elements. We also consider the general question when K is a finite field. We show that if the degree of the curve C is large enough compared to the characteristic of K, then f must be identically zero.     

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.     

CLT for Random Walks of Commuting Endomorphisms on Compact Abelian Groups

Let \(\mathcal S\) be an abelian group of automorphisms of a probability space \((X, {\mathcal A}, \mu )\) with a finite system of generators \((A_1, \ldots , A_d).\) Let \(A^{{\underline{\ell }}}\) denote \(A_1^{\ell _1} \ldots A_d^{\ell _d}\), for \({{\underline{\ell }}}= (\ell _1, \ldots , \ell _d).\) If \((Z_k)\) is a random walk on \({\mathbb {Z}}^d\), one can study the asymptotic distribution of the sums \(\sum _{k=0}^{n-1} \, f \circ A^{\,{Z_k(\omega )}}\) and \(\sum _{{\underline{\ell }}\in {\mathbb {Z}}^d} {\mathbb {P}}(Z_n= {\underline{\ell }}) \, A^{\underline{\ell }}f\), for a function f on X. In particular, given a random walk on commuting matrices in \(SL(\rho , {\mathbb {Z}})\) or in \({\mathcal M}^*(\rho , {\mathbb {Z}})\) acting on the torus \({\mathbb {T}}^\rho \), \(\rho \ge 1\), what is the asymptotic distribution of the associated ergodic sums along the random walk for a smooth function on \({\mathbb {T}}^\rho \) after normalization? In this paper, we prove a central limit theorem when X is a compact abelian connected group G endowed with its Haar measure (e.g., a torus or a connected extension of a torus), \(\mathcal S\) a totally ergodic d-dimensional group of commuting algebraic automorphisms of G and f a regular function on G. The proof is based on the cumulant method and on preliminary results on random walks.     

On height isotopy classes of embeddings in the plane of a Morse function of a circle

Let \(\mathrm{SM}_{2n}(S^1,\mathbb {R})\) be a set of stable Morse functions of an oriented circle such that the number of singular points is \(2n\in \mathbb {N}\) and the order of singular values satisfies the particular condition. For an orthogonal projection \(\pi :\mathbb {R}^2\rightarrow \mathbb {R}\), let \({\tilde{f}}_0\) and \({\tilde{f}}_1:S^1\rightarrow \mathbb {R}^2\) be embedding lifts of f. If there is an ambient isotopy \(\tilde{\varphi }_t:\mathbb {R}^2\rightarrow \mathbb {R}^2\) \((t\in [0,1])\) such that \({\pi \circ \tilde{\varphi }}_t(y_1,y_2)=y_1\) and \(\tilde{\varphi }_1\circ {\tilde{f}}_0={\tilde{f}}_1\), we say that \({\tilde{f}}_0\) and \({\tilde{f}}_1\) are height isotopic. We define a function \(I:\mathrm{SM}_{2n}(S^1,\mathbb {R})\rightarrow \mathbb {N}\) as follows: I(f) is the number of height isotopy classes of embeddings such that each rotation number is one. In this paper, we determine the maximal value of the function I equals the n-th Baxter number and the minimal value equals \(2^{n-1}\).     

The cohomology of orbit spaces of certain free circle group actions

Suppose that \(G =\mathbb{S}^1\) acts freely on a finitistic space X whose (mod p) cohomology ring is isomorphic to that of a lens space \(L^{2m-1}(p;q_1,\ldots,q_m)\) or \(\mathbb{S}^1\times \mathbb{C}P^{m-1}\). The mod p index of the action is defined to be the largest integer n such that α ⁿ ?≠?0, where \(\alpha \,\epsilon\, H^2(X/G;\mathbb{Z}_p)\) is the nonzero characteristic class of the \(\mathbb{S}^1\)-bundle \(\mathbb{S}^1\hookrightarrow X\rightarrow X/G\). We show that the mod p index of a free action of G on \(\mathbb{S}^1\times \mathbb{C}P^{m-1}\) is p???1, when it is defined. Using this, we obtain a Borsuk–Ulam type theorem for a free G-action on \(\mathbb{S}^1\times \mathbb{C}P^{m-1}\). It is note worthy that the mod p index for free G-actions on the cohomology lens space is not defined.     

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\} \).     

On some constacyclic codes over $$\mathbb {Z}_{4}\left[ u\right] /\left\langle u^{2}-1\right\rangle $$, their $$\mathbb {Z}_4$$Z4 images,and new codes

In this paper, we study \(\lambda \)-constacyclic codes over the ring \(R=\mathbb {Z}_4+u\mathbb {Z}_4\) where \(u^{2}=1\), for \(\lambda =3+2u\) and \(2+3u\). Two new Gray maps from R to \(\mathbb {Z}_4^{3}\) are defined with the goal of obtaining new linear codes over \(\mathbb {Z}_4\). The Gray images of \(\lambda \)-constacyclic codes over R are determined. We then conducted a computer search and obtained many \(\lambda \)-constacyclic codes over R whose \(\mathbb {Z}_4\)-images have better parameters than currently best-known linear codes over \(\mathbb {Z}_4\).     

Approximation of entire functions of exponential type by exponential sums<Superscript>*</Superscript>

Let K be a compact set in \( {{\mathbb R}^n} \). For \( 1 \leqslant p \leqslant \infty \), the Bernstein space \( B_K^p \) is the Banach space of all functions \( f \in {L^p}\left( {{{\mathbb R}^n}} \right) \)such that their Fourier transform in a distributional sense is supported on K. If \( f \in B_K^p \), then f is continuous on \( {{\mathbb R}^n} \) and has an extension onto the complex space \( {{\mathbb C}^n} \) to an entire function of exponential type K. We study the approximation of functions in \( B_K^p \) by finite τ -periodic exponential sums of the form

$ \sum\limits_m {{c_m}{e^{2\pi {\text{i}}\left( {x,m} \right)/\tau }}} $

in the \( {L^p}\left( {\tau {{\left[ { - 1/2,1/2} \right]}^n}} \right) \)-norm as τ → ∞ when K is a polytope in \( {{\mathbb R}^n} \).

     

$$L^{p}$$-Norms a nd Mahler’s Measure of Poly nomials o n the n-Dime nsio nal Torus

We prove Nikol’skii type inequalities that, for polynomials on the n-dimensional torus \(\mathbb {T}^n\), relate the \(L^p\)-norm with the \(L^q\)-norm (with respect to the normalized Lebesgue measure and \(0 <p <q < \infty \)). Among other things, we show that \(C=\sqrt{q/p}\) is the best constant such that \(\Vert P\Vert _{L^q}\le C^{\text {deg}(P)} \Vert P\Vert _{L^p}\) for all homogeneous polynomials P on \(\mathbb {T}^n\). We also prove an exact inequality between the \(L^p\)-norm of a polynomial P on \(\mathbb {T}^n\) and its Mahler measure M(P), which is the geometric mean of |P| with respect to the normalized Lebesgue measure on \(\mathbb {T}^n\). Using extrapolation, we transfer this estimate into a Khintchine–Kahane type inequality, which, for polynomials on \(\mathbb {T}^n\), relates a certain exponential Orlicz norm and Mahler’s measure. Applications are given, including some interpolation estimates.     

On the 2-adic valuation of the cardinality of elliptic curves over finite extensions of $$\mathbb {F}_{\varvec{q}} $$

In this paper we study the difference between the 2-adic valuations of the cardinalities \( \# E( \mathbb {F}_{q^k} ) \) and \( \# E( \mathbb {F}_q ) \) of an elliptic curve E over \( \mathbb {F}_q \). We also deduce information about the structure of the 2-Sylow subgroup \( E[ 2^\infty ]( \mathbb {F}_{q^k} ) \) from the exponents of \( E[ 2^\infty ]( \mathbb {F}_q ) \).     

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.

     

Analytic sets and extension of holomorphic maps of positive codimension

Let D, \(D'\) be arbitrary domains in \({\mathbb C}^n\) and \({\mathbb C}^N\) respectively, \(1<n\le N\), both possibly unbounded and \(M \subseteq \partial D\), \(M'\subseteq \partial D'\) be open pieces of the boundaries. Suppose that \(\partial D\) is smooth real-analytic and minimal in an open neighborhood of \({\bar{M}}\) and \(\partial D'\) is smooth real-algebraic and minimal in an open neighborhood of \({\bar{M}'}\). Let \(f: D\rightarrow D'\) be a holomorphic mapping such that the cluster set \(\mathrm{cl}_{f}(M)\) does not intersect \(D'\). It is proved that if the cluster set \(\mathrm{cl}_{f}(p)\) of some point \(p\in M\) contains some point \(q\in M'\) and the graph of f extends as an analytic set to a neighborhood of \((p, q)\in {\mathbb {C}}^n \times {\mathbb C}^N\), then f extends as a holomorphic map to a dense subset of some neighborhood of p. If in addition, \(M =\partial D\), \(M'=\partial D'\) and \(M'\) is compact, then f extends holomorphically across an open dense subset of \(\partial D\).     

Sandwich semigroups in locally small categories I: foundations

Fix (not necessarily distinct) objects i and j of a locally small category S, and write \(S_{ij}\) for the set of all morphisms \(i\rightarrow j\). Fix a morphism \(a\in S_{ji}\), and define an operation \(\star _a\) on \(S_{ij}\) by \(x\star _ay=xay\) for all \(x,y\in S_{ij}\). Then \((S_{ij},\star _a)\) is a semigroup, known as a sandwich semigroup, and denoted by \(S_{ij}^a\). This article develops a general theory of sandwich semigroups in locally small categories. We begin with structural issues such as regularity, Green’s relations and stability, focusing on the relationships between these properties on \(S_{ij}^a\) and the whole category S. We then identify a natural condition on a, called sandwich regularity, under which the set \({\text {Reg}}(S_{ij}^a)\) of all regular elements of \(S_{ij}^a\) is a subsemigroup of \(S_{ij}^a\). Under this condition, we carefully analyse the structure of the semigroup \({\text {Reg}}(S_{ij}^a)\), relating it via pullback products to certain regular subsemigroups of \(S_{ii}\) and \(S_{jj}\), and to a certain regular sandwich monoid defined on a subset of \(S_{ji}\); among other things, this allows us to also describe the idempotent-generated subsemigroup \(\mathbb E(S_{ij}^a)\) of \(S_{ij}^a\). We also study combinatorial invariants such as the rank (minimal size of a generating set) of the semigroups \(S_{ij}^a\), \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\); we give lower bounds for these ranks, and in the case of \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\) show that the bounds are sharp under a certain condition we call MI-domination. Applications to concrete categories of transformations and partial transformations are given in Part II.     

Spectral density estimates with partial symmetries and an application to Bahri–Lions-type results

We are concerned with the existence of infinitely many solutions for the problem \(-\Delta u=|u|^{p-2}u+f\) in \(\Omega \), \(u=u_0\) on \(\partial \Omega \), where \(\Omega \) is a bounded domain in \(\mathbb {R}^N\), \(N\ge 3\). This can be seen as a perturbation of the problem with \(f=0\) and \(u_0=0\), which is odd in u. If \(\Omega \) is invariant with respect to a closed strict subgroup of O(N), then we prove infinite existence for all functions f and \(u_0\) in certain spaces of invariant functions for a larger range of exponents p than known before. In order to achieve this, we prove Lieb–Cwikel–Rosenbljum-type bounds for invariant potentials on \(\Omega \), employing improved Sobolev embeddings for spaces of invariant functions.     

Some results on linear codes over the ring $$\mathbb {Z}_4+u\mathbb {Z}_4+v\mathbb {Z}_4+uv\mathbb {Z}_4$$

In this paper, we mainly study the theory of linear codes over the ring \(R =\mathbb {Z}_4+u\mathbb {Z}_4+v\mathbb {Z}_4+uv\mathbb {Z}_4\). By using the Chinese Remainder Theorem, we prove that R is isomorphic to a direct sum of four rings. We define a Gray map \(\Phi \) from \(R^{n}\) to \(\mathbb {Z}_4^{4n}\), which is a distance preserving map. The Gray image of a cyclic code over R is a linear code over \(\mathbb {Z}_4\). We also discuss some properties of MDS codes over R. Furthermore, we study the MacWilliams identities of linear codes over R and give the generator polynomials of cyclic codes over R.     

Computing Explicit Isomorphisms with Full Matrix Algebras over $$\mathbb {F}_q(x)$$

We propose a polynomial time f-algorithm (a deterministic algorithm which uses an oracle for factoring univariate polynomials over \(\mathbb {F}_q\)) for computing an isomorphism (if there is any) of a finite-dimensional \(\mathbb {F}_q(x)\)-algebra \(\mathcal{A}\) given by structure constants with the algebra of n by n matrices with entries from \(\mathbb {F}_q(x)\). The method is based on computing a finite \(\mathbb {F}_q\)-subalgebra of \(\mathcal{A}\) which is the intersection of a maximal \(\mathbb {F}_q[x]\)-order and a maximal R-order, where R is the subring of \(\mathbb {F}_q(x)\) consisting of fractions of polynomials with denominator having degree not less than that of the numerator.     

Generating Hyperbolic Singularities in Semitoric Systems Via Hopf Bifurcations

Let \((M,\Omega )\) be a connected symplectic 4-manifold and let \(F=(J,H) :M\rightarrow \mathbb {R}^2\) be a completely integrable system on M with only non-degenerate singularities. Assume that F does not have singularities with hyperbolic blocks and that \(p_1,\ldots ,p_n\) are the focus–focus singularities of F. For each subset \(S=\{i_1,\ldots ,i_j\}\), we will show how to modify F locally around any \(p_i, i \in S\), in order to create a new integrable system \(\widetilde{F}=(J, \widetilde{H}) :M \rightarrow \mathbb {R}^2\) such that its classical spectrum \(\widetilde{F}(M)\) contains j smooth curves of singular values corresponding to non-degenerate transversally hyperbolic singularities of \(\widetilde{F}\). Moreover the focus–focus singularities of \(\widetilde{F}\) are precisely \(p_i\), \(i \in \{1,\ldots ,n\} \setminus S\). The proof is based on Eliasson’s linearization theorem for non-degenerate singularities, and properties of the Hamiltonian Hopf bifurcation.     

Slow escaping points of quasiregular mappings

This article concerns the iteration of quasiregular mappings on \(\mathbb {R}^d\) and entire functions on \(\mathbb {C}\). It is shown that there are always points at which the iterates of a quasiregular map tend to infinity at a controlled rate. Moreover, an asymptotic rate of escape result is proved that is new even for transcendental entire functions. Let \(f:\mathbb {R}^d\rightarrow \mathbb {R}^d\) be quasiregular of transcendental type. Using novel methods of proof, we generalise results of Rippon and Stallard in complex dynamics to show that the Julia set of f contains points at which the iterates \(f^n\) tend to infinity arbitrarily slowly. We also prove that, for any large R, there is a point x with modulus approximately R such that the growth of \(|f^n(x)|\) is asymptotic to the iterated maximum modulus \(M^{n}(R,f)\).