Mixing time of an unaligned Gibbs sampler on the square

The paper concerns a particular example of the Gibbs sampler and its mixing efficiency. Coordinates of a point are rerandomized in the unit square ${[0,1]}^2$ to approach a stationary distribution with density proportional to $exp(?A^2{(u?v)}^2)$ for $(u,v)\in {[0,1]}^2$ with some large parameter $A$.Diaconis conjectured the mixing time of this process to be $O\left(A^2\right)$ which we confirm in this paper. This improves on the currently known $O(exp\left(A^2\right))$ estimate.     

On a problem of Specker about Euclidean representations of finite graphs

Say that a graph $G$ is representable in ${\mathbb{R}}^n$ if there is a map $f$ from its vertex set into the Euclidean space ${\mathbb{R}}^n$ such that $6f\left(x\right)?f\left(x^{\prime }\right)6=6f\left(y\right)?f\left(y^{\prime }\right)6$ iff $\{x,x^{\prime }\}$ and$\{y,y^{\prime }\}$ are both edges or both non-edges in $G$. The purpose of this note is to present the proof of the following result, due to Einhorn and Schoenberg in Einhorn and Schoenberg (1966): if $G$ finite is neither complete nor independent, then it is representable in ${\mathbb{R}}^{\left|G\right|?2}$. A similar result also holds in the case of finite complete edge-colored graphs.     

The combinatorial properties of the Benoumhani polynomials for the Whitney numbers of Dowling lattices

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials $F_{m,n,1}\left(x\right)$ and $F_{m,n,2}\left(x\right)$. Then, he defined $A_m(n,k)$ and $B_m(n,k)$ to be the polynomials satisfying $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{A}_m(n,k)x^{n?k}{(x+1)}^k$ and $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{B}_m(n,k)x^{n?k}{(x+1)}^k$. In this paper, we give a combinatorial interpretation of the coefficients of $A_{m+1}(n,k)$ and prove a symmetry of the coefficients, i.e., $\left[m^s\right]A_{m+1}(n,k)=\left[m^{n?s}\right]A_{m+1}(n,n?k)$. We give a combinatorial interpretation of $B_{m+1}(n,k)$ and prove that $B_{m+1}(n,n?1)$ is a polynomial in $m$ with non-negative integer coefficients. We also prove that if $n\ge 6$ then all coefficients of $B_{m+1}(n,n?2)$ except the coefficient of $m^{n?1}$ are non-negative integers. For all $n$, the coefficient of $m^{n?1}$ in $B_{m+1}(n,n?2)$ is $?(n?1)$, and when $n\le 5$ some other coefficients of $B_{m+1}(n,n?2)$ are also negative.     

New results on permutation binomials of finite fields

After a brief review of the existing results on permutation binomials of finite fields, we introduce the notion of equivalence among permutation binomials (PBs) and describe how to bring a PB to its canonical form under equivalence. We then focus on PBs of ${\mathbb{F}}_{q^2}$ of the form $X^n(X^{d(q-1)}+a)$, where n and d are positive integers and $a\in {\mathbb{F}}_{q^2}^{⁎}$. Our contributions include two nonexistence results: (1) If q is even and sufficiently large and $a^{q+1}\ne 1$, then $X^n(X^{3(q-1)}+a)$ is not a PB of ${\mathbb{F}}_{q^2}$. (2) If $2\le d|q+1$, q is sufficiently large and $a^{q+1}\ne 1$, then $X^n(X^{d(q-1)}+a)$ is not a PB of ${\mathbb{F}}_{q^2}$ under certain additional conditions. (1) partially confirms a recent conjecture by Tu et al. (2) is an extension of a previous result with $n=1$.     

Complete permutation polynomials with the form (xpm−x+δ)s+axpm+bx over Fpn

In this paper, several classes of complete permutation polynomials with the form ${(x^{p^m}-x+\delta )}^s+a{x}^{p^m}+bx$ over ${\mathbb{F}}_{p^n}$ are proposed by the AGW criterion and determining the number of solutions of some equations. Our results also enrich constructions of known permutation polynomials.     

Moser–Trudinger inequality involving the anisotropic Dirichlet norm (∫ΩFN(∇u)dx)1N on W01,N(Ω)

We investigate a sharp Moser–Trudinger inequality which involves the anisotropic Dirichlet norm ${({\int }_{\mathrm{\Omega }}{F}^N(\mathrm{?}u)dx)}^{\frac{1}{N}}$ on $W_0^{1,N}(\mathrm{\Omega })$ for $N\ge 2$. Here F is convex and homogeneous of degree 1, and its polar $F^o$ represents a Finsler metric on ${\mathbb{R}}^N$. Under this anisotropic Dirichlet norm, we establish the Lions type concentration-compactness alternative. Then by using a blow-up procedure, we obtain the existence of extremal functions for this sharp geometric inequality.     

Characterizations and constructions of n-to-1 mappings over finite fields

n-to-1 mappings have wide applications in many areas, especially in cryptography, finite geometry, coding theory and combinatorial design. In this paper, many classes of n-to-1 mappings over finite fields are studied. First, we provide a characterization of general n-to-1 mappings over ${\mathbb{F}}_{p^m}$ by means of the Walsh transform. Then, we completely determine 3-to-1 polynomials with degree no more than 4 over ${\mathbb{F}}_{p^m}$. Furthermore, we obtain an AGW-like criterion for characterizing some close relationship between the n-to-1 property of a mapping over finite set A and that of another mapping over a subset of A. Finally, we apply the AGW-like criterion into several forms of polynomials and obtain some explicit n-to-1 mappings. Especially, three explicit constructions of the form $x^{r}h\left(x^s\right)$ from the cyclotomic perspective, and several classes of n-to-1 mappings of the form $g(x^{q^k}-x+\delta )+cx$ are provided.     

Perfect squares representing the number of rational points on elliptic curves over finite field extensions

Let q be a perfect power of a prime number p and $E({\mathbb{F}}_q)$ be an elliptic curve over ${\mathbb{F}}_q$ given by the equation $y^2=x^3+Ax+B$. For a positive integer n we denote by $\mathrm{\#}E({\mathbb{F}}_{q^n})$ the number of rational points on E (including infinity) over the extension ${\mathbb{F}}_{q^n}$. Under a mild technical condition, we show that the sequence ${\{\mathrm{\#}E({\mathbb{F}}_{q^n})\}}_{n>0}$ contains at most 10²⁰⁰ perfect squares. If the mild condition is not satisfied, then $\mathrm{\#}E({\mathbb{F}}_{q^n})$ is a perfect square for infinitely many n including all the multiples of 12. Our proof uses a quantitative version of the Subspace Theorem. We also find all the perfect squares for all such sequences in the range $q<50$ and $n\le 1000$.