On a question of Sárközy on gaps of product sequences

Motivated by a question of Sárközy, we study the gaps in the product sequence B = A · A = {b ₁ < b ₂ < …} of all products a _i a _j with a _i , a _j ∈ A when A has upper Banach density α > 0. We prove that there are infinitely many gaps b _n+1 ? b _n ? α ^?3 and that for t ≥ 2 there are infinitely many t-gaps b _n+t ? b _n ? t ² α ^?4. Furthermore, we prove that these estimates are best possible.We also discuss a related question about the cardinality of the quotient set A/A = {a _i /a _j , a _i , a _j ∈ A} when A ? {1, …, N} and |A| = αN.     

Optimum super-simple mixed covering arrays of type <Emphasis Type="Italic">a</Emphasis><Superscript>1</Superscript><Emphasis Type="Italic">b</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis>−1</Superscript>

A mixed covering array (MCA) of type (_v 1, v ₂,..., v _k ), denoted by MCA_λ (N; t, k, (v ₁, v ₂,..., v _k )), is an N × k array with entries in the i-th column from a set _{V i} of v _i symbols and has the property that each N × t sub-array covers all the t-tuples at least λ times, where 1 ≤ i ≤ k. An MCA _λ (N; t, k, (_v 1, v ₂,..., v _k )) is said to be super-simple, if each of its N × (t + 1) sub-arrays contains each (t + 1)-tuple at most once. Recently, it was proved by Tang, Yin and the author that an optimum super-simple MCA of type (a, b, b,..., b) is equivalent to a mixed detecting array (DTA) of type (a, b, b,..., b) with optimum size. Such DTAs can be used to generate test suites to identify and determine the interaction faults between the factors in a component-based system. In this paper, some combinatorial constructions of optimum super-simple MCAs of type (a, b, b,..., b) are provided. By employing these constructions, some optimum super-simple MCAs are then obtained. In particular, the spectrum across which optimum super-simple MCA₂(2b ²; 2, 4, (a, b, b, b))′s exist, is completely determined, where 2 ≤ a ≤ b.     

Semigroup and Metric Characteristics of Locally Primitive Matrices and Digraphs

The notion of local primitivity for a quadratic 0, 1-matrix of size n × n is extended to any part of the matrix which need not be a rectangular submatrix. A similar generalization is carried out for any set B of pairs of initial and final vertices of the paths in an n-vertex digraph, B ? {(i, j) : 1 ≤ i, j ≤ n}. We establish the relationship between the local B-exponent of a matrix (digraph) and its characteristics such as the cyclic depth and period, the number of nonprimitive matrices, and the number of nonidempotentmatrices in the multiplicative semigroup of all quadratic 0, 1-matrices of order n, etc. We obtain a criterion of B-primitivity and an upper bound for the B-exponent. We also introduce some new metric characteristics for a locally primitive digraph Γ: the k, r-exporadius, the k, r-expocenter, where 1 ≤ k, r ≤ n, and the matex which is defined as the matrix of order n of all local exponents in the digraph Γ. An example of computation of the matex is given for the n-vertex Wielandt digraph. Using the introduced characteristics, we propose an idea for algorithmically constructing realizable s-boxes (elements of round functions of block ciphers) with a relatively wide range of sizes.     

Turán-Type Results for Complete <Emphasis Type="Italic">h</Emphasis>-Partite Graphs in Comparability and Incomparability Graphs

We consider an h-partite version of Dilworth’s theorem with multiple partial orders. Let P be a finite set, and let <₁,...,< _r be partial orders on P. Let G(P, <₁,...,< _r ) be the graph whose vertices are the elements of P, and x, y ∈ P are joined by an edge if x< _i y or y< _i x holds for some 1 ≤ i ≤ r. We show that if the edge density of G(P, <₁, ... , < _r ) is strictly larger than 1 ? 1/(2h ? 2) ^r , then P contains h disjoint sets A ₁, ... , A _h such that A ₁ < _j ... < _j A _h holds for some 1 ≤ j ≤ r, and |A ₁| = ... = |A _h | = Ω(|P|). Also, we show that if the complement of G(P, <) has edge density strictly larger than 1 ? 1/(3h ? 3), then P contains h disjoint sets A ₁, ... , A _h such that the elements of A _i are incomparable with the elements of A _j for 1 ≤ i < j ≤ h, and |A ₁| = ... = |A _h | = |P|^1?o(1). Finally, we prove that if the edge density of the complement of G(P, <₁, <₂) is α, then there are disjoint sets A, B ? P such that any element of A is incomparable with any element of B in both <₁ and <₂, and |A| = |B| > n ^1?γ(α), where γ(α) → 0 as α → 1. We provide a few applications of these results in combinatorial geometry, as well.     

Homological Epimorphisms, Compactly Generated t-Structures and Gorenstein-Projective Modules

The aim of this paper is two-fold. Given a recollement (T′, T, T″, i*, i_*, i^!, j_!, j*, j_*), where T′, T, T″ are triangulated categories with small coproducts and T is compactly generated. First, the authors show that the BBD-induction of compactly generated t-structures is compactly generated when i_* preserves compact objects. As a con-sequence, given a ladder (T′, T, T″, T, T′) of height 2, then the certain BBD-induction of compactly generated t-structures is compactly generated. The authors apply them to the recollements induced by homological ring epimorphisms. This is the first part of their work. Given a recollement (D(B-Mod),D(A-Mod),D(C-Mod), i*, i_*, i^!, j_!, j*, j_*) induced by a homological ring epimorphism, the last aim of this work is to show that if A is Gorenstein, _A B has finite projective dimension and j_! restricts to D ^b (C-mod), then this recollement induces an unbounded ladder (B-Gproj,A-Gproj, C-Gproj) of stable categories of finitely generated Gorenstein-projective modules. Some examples are described.     

Bivariate Binomial Moments and Bonferroni-Type Inequalities

We obtain bivariate forms of Gumbel’s, Fréchet’s and Chung’s linear inequalities for P(S ≥ u, T ≥ v) in terms of the bivariate binomial moments {S _{i, j} }, 1 ≤ i ≤ k,1 ≤ j ≤ l of the joint distribution of (S, T). At u = v = 1, the Gumbel and Fréchet bounds improve monotonically with non-decreasing (k, l). The method of proof uses combinatorial identities, and reveals a multiplicative structure before taking expectation over sample points.     

Some new sums related to D. H. Lehmer problem

About Lehmer’s number, many people have studied its various properties, and obtained a series of interesting results. In this paper, we consider a generalized Lehmer problem: Let p be a prime, and let N(k; p) denote the number of all 1 ? a _i ? p ? 1 such that a ₁ a ₂ … a _k ≡ 1 mod p and 2 | a _i + ā _i + 1, i = 1, 2, …, k. The main purpose of this paper is using the analytic method, the estimate for character sums and trigonometric sums to study the asymptotic properties of the counting function N(k; p), and give an interesting asymptotic formula for it.     

Block partitions: an extended view

Given a sequence \({S=(s_1, \ldots,s_m) \in [0, 1]^m}\), a block B of S is a subsequence \({B=(s_i,s_{i+1}, \ldots,s_j)}\). The size b of a block B is the sum of its elements. It is proved in [1] that for each positive integer n, there is a partition of S into n blocks B₁, \({\ldots,}\) B _n with \({|b_i - b_j| \le 1}\) for every i, j. In this paper, we consider a generalization of the problem in higher dimensions.     

The Number of <Emphasis Type="Italic">k</Emphasis>-Sumsets in an Abelian Group

Let G be an abelian group of order n. The sum of subsets A₁,...,A_k of G is defined as the collection of all sums of k elements from A₁,...,A_k; i.e., A₁ + A₂ + · · · + A_k = {a₁ + · · · + a_k | a₁ ∈ A₁,..., a_k ∈ A_k}. A subset representable as the sum of k subsets of G is a k-sumset. We consider the problem of the number of k-sumsets in an abelian group G. It is obvious that each subset A in G is a k-sumset since A is representable as A = A₁ + · · · + A_k, where A₁ = A and A₂ = · · · = A_k = {0}. Thus, the number of k-sumsets is equal to the number of all subsets of G. But, if we introduce a constraint on the size of the summands A₁,...,A_k then the number of k-sumsets becomes substantially smaller. A lower and upper asymptotic bounds of the number of k-sumsets in abelian groups are obtained provided that there exists a summand A_i such that |A_i| = n log^qn and |A₁ +· · ·+ A_i-1 + A_i+1 + · · ·+A_k| = n log^qn, where q = -1/8 and i ∈ {1,..., k}.     

Bent functions with stronger nonlinear properties: K-bent functions

We introduce the notion of k-bent function, i.e., a Boolean functionwith evennumber m of variables υ ₁, …, υ _m which can be approximated with all functions of the form 〈u, v〉 _j ⊕ a in the equally poor manner, where u ∈ ? ₂ ^m , a ∈ ?₂, and 1 ? j ? k. Here 〈·, ·〉 _j is an analog of the inner product of vectors; k changes from 1 to m/2. The operations 〈·, ·〉 _k , 1 ? k ? m/2, are defined by using the special series of binary Hadamard-like codes A _m ^k of length 2 ^m . Namely, the vectors of values for the functions 〈u, v〉 _k ⊕ a are codewords of the code A _m ^k . The codes A _m ^k are constructed using subcodes of the ?₄-linear Hadamard-like codes of length 2 ^m+1, which were classified by D. S. Krotov (2001). At that the code A _m ¹ is linear and A _m ¹ , …, A _m ^m/2 are pairwise nonequivalent. On the codewords of a code A _m ^k , we define a group operation ? coordinated with the Hamming metric. That is why we can consider k-bent functions as functions that are maximal nonlinear in k distinct senses of linearity at the same time. Bent functions in usual sense coincide with 1-bent functions. For k > ? ? 1, the class of k-bent functions is a proper subclass of the class of ?-bent functions. In the paper, we give methods for constructing k-bent functions and study their properties. It is shown that there exist k-bent functions with an arbitrary algebraic degree d, where 2 ? d ? max {2, m/2 ? k + 1}. Given an arbitrary k, we define the subset \(\mathfrak{F}_m^k \mathcal{F}_m^k \) of the set \(\mathfrak{F}_m^k \mathcal{F}_m^k \) \(\mathcal{A}_m^k \mathcal{B}_m^k \) of all Boolean functions in m variables with the following property: on this subset k-bent functions and 1-bent functions coincide.     

Asymptotic behavior of the spectrum of one-dimensional vibrations in a layered medium consisting of elastic and Kelvin–Voigt viscoelastic materials

For every algebraically closed field k of characteristic different from 2, we prove the following: (1) Finite-dimensional (not necessarily associative) k-algebras of general type of a fixed dimension, considered up to isomorphism, are parametrized by the values of a tuple of algebraically independent (over k) rational functions of the structure constants. (2) There exists an “algebraic normal form” to which the set of structure constants of every such algebra can be uniquely transformed by means of passing to its new basis—namely, there are two finite systems of nonconstant polynomials on the space of structure constants, {f_i}i∈I and {b_j}j∈J, such that the ideal generated by the set {f_i}i∈I is prime and, for every tuple c of structure constants satisfying the property b_j(c) ≠ 0 for all j ∈ J, there exists a unique new basis of this algebra in which the tuple c′ of its structure constants satisfies the property f_i(c′) = 0 for all i ∈ I.     

Polyboxes,Cube Tilings and Rigidity

A non-empty subset A of X=X ₁×???×X _d is a (proper) box if A=A ₁×???×A _d and A _i ?X _i for each i. Suppose that for each pair of boxes A, B and each i, one can only know which of the three states takes place: A _i =B _i , A _i =X _i ?B _i , A _i ?{B _i ,X _i ?B _i }. Let F and G be two systems of disjoint boxes. Can one decide whether ∪F=∪G? In general, the answer is ‘no’, but as is shown in the paper, it is ‘yes’ if both systems consist of pairwise dichotomous boxes. (Boxes A, B are dichotomous if there is i such that A _i =X _i ?B _i .) Several criteria that enable to compare such systems are collected. The paper includes also rigidity results, which say what assumptions have to be imposed on F to ensure that ∪F=∪G implies F=G. As an application, the rigidity conjecture for 2-extremal cube tilings of Lagarias and Shor is verified.     

Finite configurations in sparse sets

Let E ? ?ⁿ be a closed set of Hausdorff dimension α. For m > n, let{B₁, …, B_k} be n × (m ? n) matrices. We prove that if the system of matrices B_j is non-degenerate in a suitable sense, α is sufficiently close to n, and if E supports a probability measure obeying appropriate dimensionality and Fourier decay conditions, then for a range of m depending on n and k, the set E contains a translate of a non-trivial k-point configuration {B₁y, …, B_ky}. As a consequence, we are able to establish existence of certain geometric configurations in Salem sets (such as parallelograms in ?ⁿ and isosceles right triangles in ?²). This can be viewed as a multidimensional analogue of the result of [25] on 3-term arithmetic progressions in subsets of ?.     

When does the zero-one <Emphasis Type="Italic">k</Emphasis>-law fail?

The limit probabilities of the first-order properties of a random graph in the Erd?s–Rényi model G(n, n^?α), α ∈ (0, 1), are studied. A random graph G(n, n^?α) is said to obey the zero-one k-law if, given any property expressed by a formula of quantifier depth at most k, the probability of this property tends to either 0 or 1. As is known, for α = 1? 1/(2^k?1 + a/b), where a > 2^k?1, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2^k?1 ? 2. It is proved that the k-law also fails for b > 1 and a ≤ 2^k?1 ? (b + 1)².     

Equations in finite fields with restricted solution sets. I (Character sums)

In earlier papers, for “large” (but otherwise unspecified) subsets A, B of Z _p and for h(x) ∈ Z _p [x], Gyarmati studied the solvability of the equations a + b = h(x), resp. ab = h(x) with a ∈ A, b ∈ B, x ∈ Z _p , and for large subsets A, B, C, D of Z _p Sárközy showed the solvability of the equations a + b = cd, resp. ab + 1 = cd with a ∈ A, b ∈ B, c ∈ C, d ∈ D. In this series of papers equations of this type will be studied in finite fields. In particular, in Part I of the series we will prove the necessary character sum estimates of independent interest some of which generalize earlier results.     

Consecutive integers in high-multiplicity sumsets

Sharpening (a particular case of) a result of Szemerédi and Vu [4] and extending earlier results of Sárközy [3] and ourselves [2], we find, subject to some technical restrictions, a sharp threshold for the number of integer sets needed for their sumset to contain a block of consecutive integers, whose length is comparable with the lengths of the set summands.A corollary of our main result is as follows. Let k,l≥1 and n≥3 be integers, and suppose that A ₁,…,A _k ?[0,l] are integer sets of size at least n, none of which is contained in an arithmetic progression with difference greater than 1. If k≥2?(l?1)/(n?2)?, then the sumset A ₁+???+A _k contains a block of at least k(n?1)+1 consecutive integers.     

Boundary value problem with normal derivatives for a higher-order elliptic equation on the plane

For an elliptic operator of order 2l with constant (and only leading) real coefficients, we consider a boundary value problem in which the normal derivatives of order (k _j ?1), j = 1,..., l, where 1 ≤ k ₁ < ··· < k _l, are specified. It becomes the Dirichlet problem for kj = j and the Neumann problem for k _j = j + 1. We obtain a sufficient condition for the Fredholm property of which problem and derive an index formula.     

A gradual rank increasing process for matrix completion

The matrix completion problem is easy to state: let A be a given data matrix in which some entries are unknown. Then, it is needed to assign “appropriate values” to these entries. A common way to solve this problem is to compute a rank-k matrix, B _k , that approximates A in a least squares sense. Then, the unknown entries in A attain the values of the corresponding entries in B _k . This raises the question of how to determine a suitable matrix rank. The method proposed in this paper attempts to answer this question. It builds a finite sequence of matrices \(B_{k}, k = 1, 2, \dots \), where B _k is a rank-k matrix that approximates A in a least squares sense. The computational effort is reduced by using B _k-1 as starting point in the computation of B _k . The ability of B _k to serve as substitute for A is measured with two objective functions: a “training” function that measures the distance between the known part of A and the corresponding part of B _k , and a “probe” function that assesses the quality of the imputed entries. Watching the changes in these functions as k increases enables us to find an optimal matrix rank. Numerical experiments illustrate the usefulness of the proposed approach.     

A Probabilistic Characterization of the Dominance Order on Partitions

We present a probabilistic characterization of the dominance order on partitions. Let ν be a partition and Y _ν its Ferrers diagram, i.e. a stack of rows of cells with row i containing ν _i cells. Let the cells of Y _ν be filled with independent and identically distributed draws from the random variable X = B i n(r, p) with r ≥ 1 and p ∈ (0, 1). Given j, t ≥ 0, let P(ν, j, t) be the probability that the sum of all the entries in Y _ν is j while the sum of the entries in each row of Y _ν is no more than t. It is shown that if ν and μ are two partitions of n, ν dominates μ if and only if P(ν, j, t) ≤ P(μ, j, t) for all j, t ≥ 0. It is shown that the same result holds if X is any log-concave integer valued random variable with {i : P(X = i) > 0} = {0, 1,…,r} for some r ≥ 1.     

Small prime solutions to cubic equations

Let a_1,..., a_9 be nonzero integers not of the same sign, and let b be an integer. Suppose that a_1,..., a_9 are pairwise coprime and a_1 + + a_9 ≡ b(mod 2). We apply the p-adic method of Davenport to find an explicit P = P(a_1,..., a_9, n) such that the cubic equation a_1p_1~3+ + a9p_9~3= b is solvable with p_j 《 P for all 1 ≤ j ≤ 9. It is proved that one can take P = max{|a_1|,..., |a_9|}~c+ |b|~(1/3) with c = 2. This improves upon the earlier result with c = 14 due to Liu(2013).