Invertible substitutions and Sturmian sequences

It is known on the one hand that a Sturmian sequence can be generated geometrically by the intersections of a straight line with the unit grid in the plane, and on the other hand that fixed points of invertible substitutions are Sturmian. We give a new characterization of invertible substitutions, which allows to determine the straight line which generates the fixed point of a given invertible substitution.     

On the permutations generated by Sturmian words

Infinite permutations of use in this article were introduced in [1]. Here we distinguish the class of infinite permutations that are generated by the Sturmian words and inherit their properties. We find the combinatorial complexity of these permutations, describe their Rauzy graphs, frequencies of subpermutations, and recurrence functions. We also find their arithmetic complexity and Kamae complexity.     

On a question about sum-free sequences

An increasing sequence of positive integers {n₁, n₂, …} is called a sum-free sequence if every term is never a sum of distinct smaller terms. We prove that there exist sum-free sequences {n_k} with polynomial growth and such that lim_k→∞ n_k+1/n_k = 1.     

Sturmian Words and the Permutation that Orders Fractional Parts

A Sturmian word is a map W : {0,1} for which the set of {0, 1}-vectors F _n(W) {(W(i), W(i + 1),...,W(i + n – 1)) ^T : i } has cardinality exactly n + 1 for each positive integer n. Our main result is that the volume of the simplex whose n + 1 vertices are the n + 1 points in F _n(W) does not depend on W. Our proof of this motivates studying algebraic properties of the permutation _,n (where is any irrational and n is any positive integer) that orders the fractional parts {}, {2},...,{n}, i.e., 0 < {_,n (1)} < {_,n (2)} < ··· < {_,n (n)} < 1. We give a formula for the sign of _,n , and prove that for every irrational there are infinitely many n such that the order of _,n (as an element of the symmetric group S _n) is less than n.     

Regular saturated graphs and sum-free sets

In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular $K_3$-saturated graph with n vertices. We extend this result to both $K_4$ and $K_5$ and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all $k\ge 2$, there is a regular $C_{2k+1}$-saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to $C_{2k+1}$-saturated graphs is an interesting problem on its own and we state an open problem in this direction.     

On the structure of cluster point sets of iteratively generated sequences

LetX be a closed subset of a topological spaceF; leta(·) be a continuous map fromX intoX; let {x _i} be a sequence generated iteratively bya(·) fromx ₀ inX, i.e.,x _i+1 =a(x _i),i=0, 1, 2, ...; and letQ(x ₀) be the cluster point set of {x _i}. In this paper, we prove that, if there exists a pointz inQ(x ₀) such that (i)z is isolated with respect toQ(x ₀), (ii)z is a periodic point ofa(·) of periodp, and (iii)z possesses a sequentially compact neighborhood, then (iv)Q(x ₀) containsp points, (v) the sequence {x _i} is contained in a sequentially compact set, and (vi) every point inQ(x ₀) possesses properties (i) and (ii). The application of the preceding results to the caseF=E ⁿ leads to the following: (vii) ifQ(x ₀) contains one and only one point, then {x _i} converges; (viii) ifQ(x ₀) contains a finite number of points, then {x _i} is bounded; and (ix) ifQ(x ₀) containsp points, then every point inQ(x ₀) is a periodic point ofa(·) of periodp.     

Dunford-Pettis sets

Bibasic sequences are used to study relative weak compactness and relative norm compactness of Dunford-Pettis sets.

     

Zero sets and interpolating sets in Fock spaces

An example is constructed to show that interpolating sets for Fock spaces are not necessarily zero sets.

     

Graphs generated by Sidon sets and algebraic equations over finite fields

We study the spectra of several graphs generated by Sidon sets and algebraic equations over finite fields. These graphs are used to study some combinatorial problems in finite fields, such as sum product estimates, solvability of some equations and the distribution of their solutions.     

A short proof of a theorem on degree sets of graphs

For a finite simple graph G, we denote the set of degrees of its vertices, known as its degree set, by D(G). Kapoor, Polimeni and Wall [Degree sets for graphs, Fund. Math. 95 (1977) 189-194] have determined the least number of vertices among graphs with a given degree set. We give a very short proof of this result.     

A trace representation of binary Jacobi sequences

We determine the trace function representation, or equivalently, the Fourier spectral sequences of binary Jacobi sequences of period pq, where p and q are two distinct odd primes. This includes the twin-prime sequences of period p(p+2) whenever both p and p+2 are primes, corresponding to cyclic Hadamard difference sets.     

Strong characterizing sequences in simultaneous diophantine approximation

Answering a question of Liardet, we prove that if 1,α₁,α₂,…,α_t are real numbers linearly independent over the rationals, then there is an infinite subset A of the positive integers such that for real β, we have (|||| denotes the distance to the nearest integer)

     

On smooth sets of integers

This work studies evenly distributed sets of integers—sets whose quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation. Namely, for ρ,Δ∈R a set A of integers is (ρ,Δ)- smooth if for any interval I of integers; a set A is Δ-smooth if it is (ρ,Δ)-smooth for some real number ρ. The paper introduces the concept of Δ-smooth sets and studies their mathematical structure. It focuses on tools for constructing smooth sets having certain desirable properties and, in particular, on mathematical operations on these sets. Three additional papers by us are build on the work of this paper and present practical applications of smooth sets to common and well-studied scheduling problems.One of the above mathematical operations is composition of sets of natural numbers. For two infinite sets A,B⊆N, the composition of A and B is the subset D of A such that, for all i, the ith member of A is in D if and only if the ith member of N is in B. This operator enables the partition of a (ρ,Δ)-smooth set into two sets that are (ρ₁,Δ)-smooth and (ρ₂,Δ)-smooth, for any ρ₁,ρ₂ and Δ obeying some reasonable restrictions. Another powerful tool for constructing smooth sets is a one-to-one partial function f from the unit interval into the natural numbers having the property that any real interval X⊆[0,1) has a subinterval Y which is ‘very close’ to X s.t. f(Y) is (ρ,Δ)-smooth, where ρ is the length of Y and Δ is a small constant.     

On some random thin sets of integers

We show how different random thin sets of integers may have different behaviour. First, using a recent deviation inequality of Boucheron, Lugosi and Massart, we give a simpler proof of one of our results in Some new thin sets of integers in harmonic analysis, Journal d'Analyse Mathématique 86 (2002), 105-138, namely that there exist -Rider sets which are sets of uniform convergence and -sets for all but which are not Rosenthal sets. In a second part, we show, using an older result of Kashin and Tzafriri, that, for , the -Rider sets which we had constructed in that paper are almost surely not of uniform convergence.

     

On the sequence of partial maxima of some random sequences

Let {X_n, n ? 1} be a sequence of identically distributed random variables, Z_n = max {X₁,…, X_n} and {u_n, n ? 1 } an increasing sequence of real numbers. Under certain additional requirements, necessary and sufficient conditions are given to have, with probability one, an infinite number of crossings of {Z_n} with respect to {u_n}, in two cases: (1) The X_n's are independent, (2) {X_n} is stationary Gaussian and satisfies a mixing condition.     

The periods of the sequences generated by some symmetric shift registers

E_k(x₂,…, x_n) is defined by E_k(a₂,…, a_n) = 1 if and only if ∑_i=2ⁿa_i = k. We determine the periods of sequences generated by the shift registers with the feedback functions x₁ + E_k(x₂,…, x_n) and x₁ + E_k(x₂,…, x_n) + E_k+1(x₂,…, x_n) over the field GF(2).     

The geometry of some two-character sets

A projective (n, d, w ₁, w ₂) _q set (or a two-character set for short) is a set of n points of PG(d − 1, q) with the properties that the set generates PG(d − 1, q) and that every hyperplane meets the set in either n − w ₁ or n − w ₂ points. Here geometric constructions of some two-character sets are given. The constructions mainly involve commuting polarities, symplectic polarities and normal line-spreads of projective spaces. Some information about the automorphism groups of such sets is provided.