Shifts in Cayley graphs

An automorphism of an undirected simple graph is called a shift if it maps every vertex to an adjacent one. For all finite groups G, we determine the minimum nonzero valency of a Cayley graph on G that does not admit a shift. We also get a classification of groups with all involutions central and such that for every pair a,b of elements of the group, one of ab=ba, aba⁻¹=b⁻¹, bab⁻¹=a⁻¹ or a²=b^±2 holds.     

On the reducible quintic complete base polynomials

Let B(x)=xm+bm−1xm−1+?+b₀∈Z[x]. If every element in Z[x]/(B(x)Z[x]) has a polynomial representative with coefficients in S={0,1,2,…,|b₀|−1} then B(x) is called a complete base polynomial. We prove that if B(x) is a completely reducible quintic polynomial with five distinct integer roots less than −1, then B is a complete base polynomial. This is the best possible result regarding the completely reducible polynomials so far. Meanwhile, we provide a Mathematica program for determining whether an input polynomial B(x) is a complete base polynomial or not. The program enables us to experiment with various polynomial examples, to decide if the potential result points in the desired direction and to formulate credible conjectures.     

Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree

The Bermond-Thomassen conjecture states that, for any positive integer r, a digraph of minimum out-degree at least 2r−1 contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r=2, and very recently the conjecture was proved for the case where r=3. It is still open for larger values of r, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for tournaments with minimum in-degree at least 2r−1. In particular, this shows that the conjecture is true for (almost) regular tournaments. In the first proof, we prove auxiliary results about union of sets contained in another union of sets, that might be of independent interest. The second one uses a more graph-theoretical approach, by studying the properties of a maximum set of vertex-disjoint directed triangles.     

Heilbronn's conjecture on Waring's number (mod p)

Let p be a prime k|p−1, t=(p−1)/k and γ(k,p) be the minimal value of s such that every number is a sum of s kth powers . We prove Heilbronn's conjecture that γ(k,p)?k1/2 for t>2. More generally we show that for any positive integer q, γ(k,p)?C(q)k1/q for ?(t)?q. A comparable lower bound is also given. We also establish exact values for γ(k,p) when ?(t)=2. For instance, when t=3, γ(k,p)=a+b−1 where a>b>0 are the unique integers with a²+b²+ab=p, and when t=4, γ(k,p)=a−1 where a>b>0 are the unique integers with a²+b²=p.     

A binary linear recurrence sequence of composite numbers

Let (a,b)∈Z², where b≠0 and (a,b)≠(±2,−1). We prove that then there exist two positive relatively prime composite integers x₁, x₂ such that the sequence given by xn+1=axn+bxn−1, n=2,3,… , consists of composite terms only, i.e., |xn| is a composite integer for each n∈N. In the proof of this result we use certain covering systems, divisibility sequences and, for some special pairs (a,±1), computer calculations. The paper is motivated by a result of Graham who proved this theorem in the special case of the Fibonacci-like sequence, where (a,b)=(1,1).     

A note on an inverse problem for lattice points

Let K⊆R² be a compact set such that K+Z²=R² and let K−K={a−b|a,b∈K}. We prove, via Algebraic Topology, that the integer points of the difference set of K, (K−K)∩Z², is not contained on the coordinate axes, Z×{0}∪{0}×Z. This result implies the negative answer to the inverse problem posed by M.B. Nathanson (2010) [5].     

Redundant <Emphasis Type="Italic">τ</Emphasis>-adic expansions I: non-adjacent digit sets and their applications to scalar multiplication

This paper investigates some properties of τ-adic expansions of scalars. Such expansions are widely used in the design of scalar multiplication algorithms on Koblitz curves, but at the same time they are much less understood than their binary counterparts. Solinas introduced the width-w τ-adic non-adjacent form for use with Koblitz curves. This is an expansion of integers \({z = \sum_{i=0}^\ell z_i \tau^i}\) , where τ is a quadratic integer depending on the curve, such that z _i ≠ 0 implies z _w+i-1 = . . . = z _i+1 = 0, like the sliding window binary recodings of integers. It uses a redundant digit set, i.e., an expansion of an integer using this digit set need not be uniquely determined if the syntactical constraints are not enforced. We show that the digit sets described by Solinas, formed by elements of minimal norm in their residue classes, are uniquely determined. Apart from this digit set of minimal norm representatives, other digit sets can be chosen such that all integers can be represented by a width-w non-adjacent form using those digits. We describe an algorithm recognizing admissible digit sets. Results by Solinas and by Blake, Murty, and Xu are generalized. In particular, we introduce two new useful families of digit sets. The first set is syntactically defined. As a consequence of its adoption we can also present improved and streamlined algorithms to perform the precomputations in τ-adic scalar multiplication methods. The latter use an improvement of the computation of sums and differences of points on elliptic curves with mixed affine and López–Dahab coordinates. The second set is suitable for low-memory applications, generalizing an approach started by Avanzi, Ciet, and Sica. It permits to devise a scalar multiplication algorithm that dispenses with the initial precomputation stage and its associated memory space. A suitable choice of the parameters of the method leads to a scalar multiplication algorithm on Koblitz Curves that achieves sublinear complexity in the number of expensive curve operations.     

Large solutions for an elliptic system of quasilinear equations

In this paper we consider the quasilinear elliptic system Δpu=uavb, Δpv=ucve in a smooth bounded domain Ω⊂RN, with the boundary conditions u=v=+∞ on ∂Ω. The operator Δp stands for the p-Laplacian defined by Δpu=div(|∇u|^p−2∇u), p>1, and the exponents verify a,e>p−1, b,c>0 and (a−p+1)(e−p+1)?bc. We analyze positive solutions in both components, providing necessary and sufficient conditions for existence. We also prove uniqueness of positive solutions in the case (a−p+1)(e−p+1)>bc and obtain the exact blow-up rate near the boundary of the solution. In the case (a−p+1)(e−p+1)=bc, infinitely many positive solutions are constructed.     

Polynomial Cunningham chains

A sequence of prime numbers p₁,p₂,p₃,…, such that pi=2pi−1+? for all i, is called a Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the smallest positive integer such that 2pk+? is composite, then we say the chain has length k. It is conjectured that there are infinitely many Cunningham chains of length k for every positive integer k. A sequence of polynomials f₁(x),f₂(x),… in Z[x], such that f₁(x) has positive leading coefficient, each fi(x) is irreducible in Q[x] and fi(x)=xfi−1(x)+? for all i, is defined to be a polynomial Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the least positive integer such that fk+1(x) is reducible in Q[x], then we say the chain has length k. In this article, for polynomial Cunningham chains of both kinds, we prove that there are infinitely many chains of length k and, unlike the situation in the integers, that there are infinitely many chains of infinite length, by explicitly giving infinitely many polynomials f₁(x), such that fk+1(x) is the only term in the sequence that is reducible.     

Occupation games on graphs in which the second player takes almost all vertices

Given a connected graph G=(V,E), two players take turns occupying vertices v∈V by placing black and white tokens so that the current vertex sets B,W⊆V are disjoint, B∩W=0?, and the corresponding induced subgraphs G[B] and G[W] are connected any time. A player must pass whenever (s)he has no legal move. (Obviously, after this, the opponent will take all remaining vertices, since G is assumed connected.) The game is over when all vertices are taken, V=B^∗∪W^∗. Then, Black and White get b=|B^∗|/|V| and w=|W^∗|/|V|, respectively. Thus, the occupation game is one-sum, b+w=1, and we could easily reduce it to a zero-sum game by simply shifting the payoffs, b^′=b−1/2,w^′=w−1/2. Let us also notice that b≥0 and w≥0; moreover, b>0 and w>0 whenever |V|>1.[Let us remark that the so-called Chinese rules define similar payoffs for the classic game of GO, yet, the legal moves are defined in GO differently.]Like in GO, we assume that Black begins. It is easy to construct graphs in which Black can take almost all vertices, more precisely, for each ε>0 there is a graph G for which b>1−ε. In this paper we show that, somewhat surprisingly, there are also graphs in which White can take almost all vertices.     

Lower bounds for numbers of ABC-hits

By an ABC-hit, we mean a triple (a,b,c) of relatively prime positive integers such that a+b=c and rad(abc)<c. Denote by N(X) the number of ABC-hits (a,b,c) with c?X. In this paper we discuss lower bounds for N(X). In particular we prove that for every ?>0 and X large enough N(X)?exp((logX)^1/2−?).     

On the number of solutions to systems of Pell equations

We prove that, for positive integers a, b, c and d with c≠d, a>1, b>1, the number of simultaneous solutions in positive integers to ax²−cz²=1, by²−dz²=1 is at most two. This result is the best possible one. We prove a similar result for the system of equations x²−ay²=1, z²−bx²=1.     

On extremal matrices of second largest exponent by Boolean rank

Let b = b(A) be the Boolean rank of an n × n primitive Boolean matrix A and exp(A) be the exponent of A. Then exp(A) ? (b − 1)² + 2, and the matrices for which equality occurs have been determined in [D.A. Gregory, S.J. Kirkland, N.J. Pullman, A bound on the exponent of a primitive matrix using Boolean rank, Linear Algebra Appl. 217 (1995) 101-116]. In this paper, we show that for each 3 ? b ? n − 1, there are n × n primitive Boolean matrices A with b(A) = b such that exp(A) = (b − 1)² + 1, and we explicitly describe all such matrices.     

Weakly separative weakly commutative semigroups

A semigroup S is called a weakly commutative semigroup if, for every a,b∈S, there is a positive integer n such that (ab) ⁿ ∈Sa∩bS. A semigroup S is called archimedean if, for every a,b∈S, there are positive integers m and n such that a ⁿ ∈SbS and b ^m ∈SaS. It is known that every weakly commutative semigroup is a semilattice of weakly commutative archimedean semigroups. A semigroup S is called a weakly separative semigroup if, for every a,b∈S, the assumption a ²=ab=b ² implies a=b. In this paper we show that a weakly commutative semigroup is weakly separative if and only if its archimedean components are weakly cancellative. This result is a generalization of Theorem 4.16 of Clifford and Preston (The Algebraic Theory of Semigroups, Am. Math. Soc., Providence, 1961).     

Limit sets of automatic sequences

We show that for every k-automatic sequence there exists a natural number p>0 such that the sequences of the form (k^pn+j)_n?0 with j=0,…,p−1 are scaling sequences for f. Moreover, we demonstrate that every limit set is the union of certain basic limit sets.     

A polyominoes-permutations injection and tree-like convex polyominoes

Plane polyominoes are edge-connected sets of cells on the orthogonal lattice Z², considered identical if their cell sets are equal up to an integral translation. We introduce a novel injection from the set of polyominoes with n cells to the set of permutations of [n], and classify the families of convex polyominoes and tree-like convex polyominoes as classes of permutations that avoid some sets of forbidden patterns. By analyzing the structure of the respective permutations of the family of tree-like convex polyominoes, we are able to find the generating function of the sequence that enumerates this family, conclude that this sequence satisfies the linear recurrence an=6an−1−14an−2+16an−3−9an−4+2an−5, and compute the closed-form formula an=²n+2−(n³−n²+10n+4)/2.     

Complete solution of the polynomial version of a problem of Diophantus

In this paper, we prove that if {a,b,c,d} is a set of four non-zero polynomials with integer coefficients, not all constant, such that the product of any two of its distinct elements plus 1 is a square of a polynomial with integer coefficients, then

(a+b−c−d)2=4(ab+1)(cd+1).     

Chaotic dynamics in periodically forced asymmetric ordinary differential equations

Using a topological approach, we prove the existence of infinitely many periodic solutions and the presence of chaotic dynamics for the periodically forced second order ODE u^″+bu⁺−au⁻=p(t). The choice of the equation is motivated by the studies about the Dancer-Fu?ik spectrum and the Lazer-McKenna suspension bridge model.     

Multi-bump solutions to Carrier's problem

We study the existence of well-known singularly perturbed BVP problem ε²y″=1−y²−2b(1−x²)y, y(−1)=y(1)=0 introduced by G.F. Carrier. In particular, we show that there exist multi-spike solutions, and the locations of interior spikes are clustered near x=0 and are separated by an amount of O(ε|lnε|), while only single spikes are allowed near the boundaries x=±1.     

The Monotonicity of Period Function for Codimension Four Quadratic System Q4

In this paper, we study the codimension four quadratic system Q₄ : ?=−iz+4z²+2∣z∣²+(b+ic)z?², where b and c are real constants, i²=−1, z=x+iy, ∣b+ic∣=2. It is proved that the period function of periodic trajectories for Q₄ is monotone. The content of this paper can be viewed as a contribution to the proof of Chicone's conjecture (cf. MR: 94h:58072).