Search

For nonnegative integers h , g with h ≥ 2 , a set A of nonnegative integers is defined as a B h [ g ] sequence if, for every nonnegative integer n , the number of representations of n with the form n = a 1 + a 2 + ⋯ + a h is no larger than g , where a 1 ≤ ⋯ ≤ a h and a i ∈ A for i = 1 , 2 , ⋯ , h. Let Z be the set of integers and N be the set of positive integers. In 2013, by introducing the method of Inserting Zeros Transformation , Cilleruelo and Nathanson obtained the following result: let f : Z → N ⋃ { 0 , ∞ } be any function such that lim inf | n | → ∞ f (n) ≥ g and let B be any B h [ g ] sequence. Then, for any decreasing function ϵ (x) → 0 as x → ∞ , there exists a sequence A of integers such that r A , h (n) = f (n) for all n ∈ Z and A (x) ≫ B (x ϵ (x)). Recently, Nathanson further considered Sidon sets for linear forms. In this paper, we apply the Inserting Zeros Transformation into Sidon sets for linear forms and generalize the above result related to the inverse problem of representation functions. For a video summary of this paper, please visit https://youtu.be/KRtew2rLbXY. [ABSTRACT FROM AUTHOR]

The paper presents several results concerning the complexity of calculations in the model of vector addition chains. A refinement of N. Pippenger's upper bound is obtained for the complexity of the class of integer matrices with the constraint on the size of the coefficients as up to . Next, we establish an asymptotically tight bound on the complexity of сomputation of the number in the base of powers of . Based on generalized Sidon sequences, constructive examples of integer sets of cardinality are constructed: sets, with polynomial size of elements, having the complexity for any and sets, with the size of the elements, having the complexity . [ABSTRACT FROM AUTHOR]

Motivated by recent results of Tao–Ziegler [Discrete Anal. 2016] and Greenfeld–Tao (2022 preprint) on concatenating affine-linear functions along subgroups of an abelian group, we show three results on recovering affine linearity of functions f : V → W from their restrictions to affine lines, where V, W are F -vector spaces and dim V ⩾ 2 . First, if dim V < | F | and f : V → F is affine-linear when restricted to affine lines parallel to a basis and to certain "generic" lines through 0, then f is affine-linear on V. (This extends to all modules M over unital commutative rings R with large enough characteristic.) Second, we explain how a classical result attributed to von Staudt (1850 s) extends beyond bijections: If f : V → W preserves affine lines ℓ , and if f (v) ∉ f (ℓ) whenever v ∉ ℓ , then this also suffices to recover affine linearity on V, but up to a field automorphism. In particular, if F is a prime field Z / p Z ( p > 2 ) or Q , or a completion Q p or R , then f is affine-linear on V. We then quantitatively refine our first result above, via a weak multiplicative variant of the additive B h -sets initially explored by Singer [Trans. Amer. Math. Soc. 1938], Erdös–Turán [J. London Math. Soc. 1941], and Bose–Chowla [Comment. Math. Helv. 1962]. Weak multiplicative B h -sets occur inside all rings with large enough characteristic, and in all infinite or large enough finite integral domains/fields. We show that if R is among any of these classes of rings, and M = R n for some n ⩾ 3 , then one requires affine linearity on at least n ⌈ n / 2 ⌉ -many generic lines to deduce the global affine linearity of f on R n . Moreover, this bound is sharp. [ABSTRACT FROM AUTHOR]

A $(m,n)$ sonar sequence is an $m\times n$ array with exactly one dot in each column and where all lines connecting two dots in the array are distinct as vectors. These arrays are known to have many applications such as sonar and radar detection and these are studied as a particular case of Golomb rectangles or two-dimensional Sidon sets. The main open problem for sonar sequences is: for fixed $m$ , find the largest $n$ for which there is an $(m,n)$ sonar sequence, these sequences are called the best sonar sequences. The extended sonar sequences are generalizations of sonar sequences where each column has at most one dot, the motivation to study these arrays are the best results obtained when applied to radar and sonar detection. In this paper, we give the best sonar sequences with $m\leq 100$ obtained from an exhaustive computational search based on the Caicedo, Ruiz and Trujillo constructions and we present new constructions of extended sonar sequences that use Sidon sets.

Let φ (x 1 , ... , x h) = c 1 x 1 + ⋯ + c h x h be a linear form with coefficients in a field F , and let V be a vector space over F. A nonempty subset A of V is a φ-Sidon set if φ (a 1 , ... , a h) = φ (a 1 ′ , ... , a h ′) implies (a 1 , ... , a h) = (a 1 ′ , ... , a h ′) for all h -tuples (a 1 , ... , a h) ∈ A h and (a 1 ′ , ... , a h ′) ∈ A h. There exist infinite Sidon sets for the linear form φ if and only if the set of coefficients of φ has distinct subset sums. In a normed vector space with φ -Sidon sets, every infinite sequence of vectors is asymptotic to a φ -Sidon set of vectors. Results on p -adic perturbations of φ -Sidon sets of integers and bounds on the growth of φ -Sidon sets of integers are also obtained. [ABSTRACT FROM AUTHOR]

For h ≥ 2 and an infinite set of positive integers A, let R A , h (n) denote the number of representations of the positive integer n as the sum of h distinct terms from A. A set of positive integers A is called a B h [ g ] set if every positive integer can be written as the sum of h not necessarily distinct terms from A at most g different ways. We say a set A is a basis of order h if every positive integer can be represented as the sum of h terms from A. Recently, Vu [17] proved the existence of a thin basis of order h formed by perfect powers. In this paper, we study weak B h [ g ] sets formed by perfect powers. In particular, we prove the existence of a set A formed by perfect powers with almost possible maximal density such that R A , h (n) is bounded by using probabilistic methods. [ABSTRACT FROM AUTHOR]

Let h ≥ 2 and let A = (A 1 , ... , A h) be an h -tuple of sets of integers. For nonzero integers c 1 , ... , c h , consider the linear form φ = c 1 x 1 + c 2 x 2 + ⋯ + c h x h. The representation function R A , φ (n) counts the number of h -tuples (a 1 , ... , a h) ∈ A 1 × ⋯ × A h such that φ (a 1 , ... , a h) = n. The h -tuple A is a φ-Sidon system of multiplicity g if R A , φ (n) ≤ g for all n ∈ Z. For every positive integer g , let F φ , g (n) denote the largest integer q such that there exists a φ -Sidon system A = (A 1 , ... , A h) of multiplicity g with A i ⊆ [ 1 , n ] and | A i | = q for all i = 1 , ... , h. It is proved that, for all linear forms φ , lim sup n → ∞ F φ , g (n) n 1 / h < ∞ and, for linear forms φ whose coefficients c i satisfy a certain divisibility condition, lim inf n → ∞ F φ , h ! (n) n 1 / h ≥ 1. [ABSTRACT FROM AUTHOR]

We study the maximum size of Sidon sets in unions of integer intervals. If A ⊂ N is the union of two intervals and if | A | = n (where | A | denotes the cardinality of A ), we prove that A contains a Sidon set of size at least 0 , 876 n . On the other hand, by using the small differences technique, we establish a bound of the maximum size of Sidon sets in the union of k intervals. [ABSTRACT FROM AUTHOR]

Sidon spaces can be used to characterize certain multiplicative properties of subspaces. They also have important applications in cyclic subspace codes and Sidon sets. In this paper, we give three new constructions of Sidon spaces. Our results can be applied to cyclic subspace codes. As a result, we obtain some new optimal cyclic subspace codes. [ABSTRACT FROM AUTHOR]

Two new constructions for families of optical orthogonal codes are presented. The first is a generalization of the well-known construction of Sidon sets given by I. Z. Ruzsa. The second construction is optimal with respect to the Johnson bound, and its parameters $(n,w,\lambda)$ are respectively $(p^{h+1}-p,p,1)$ , where $p$ is any prime, $h$ is an integer greater than 1 and the family size is $p^{h-1}+p^{h-2}+\cdots +p^{2}+p$ .

Let k and l be positive integers satisfying $k \ge 2, l \ge 1$. A set $\mathcal {A}$ of positive integers is an asymptotic basis of order k if every large enough positive integer can be represented as the sum of k terms from $\mathcal {A}$. About 35 years ago, P. Erdős asked: does there exist an asymptotic basis of order k where all the subset sums with at most l terms are pairwise distinct with the exception of a finite number of cases as long as $l \le k - 1$ ? We use probabilistic tools to prove the existence of an asymptotic basis of order $2k+1$ for which all the sums of at most k elements are pairwise distinct except for 'small' numbers. [ABSTRACT FROM AUTHOR]

Let F q [ t ] denote the polynomial ring over F q , the finite field of q elements. Suppose the characteristic of F q is not 2 or 3. We prove that there exist infinitely many N ∈ ℕ such that the set { f ∈ F q [ t ] : deg f < N } contains a Sidon set which is an additive basis of order 3. [ABSTRACT FROM AUTHOR]

S ⊂ { 1 , 2 , ... , n } is called a Sidon set if a + b are all distinct for any a , b ∈ S. Let S n be the largest cardinal number of such S. We are interested in the sum of elements in the Sidon set S. In this paper, we prove that for any 𝜖 > 0 , ∑ a ∈ S a = 1 2 n 3 / 2 + O (n 1 1 1 / 8 0 + 𝜖) , where S ⊂ { 1 , 2 , ... , n } is a Sidon set and | S | = S n . [ABSTRACT FROM AUTHOR]

Given any n points in the plane, not all on the same line, there exist two non-collinear triples such that the ratio of the areas of the triangles they determine, differs from 1 by at most O (log n / n 2) . If we furthermore insist that the two triangles have a common edge, then there are two with area ratios differing from 1 by at most O(1/n). This improves some results of Ophir and Pinchasi (Discrete Appl. Math. 174 (2014), 122–127). We also give some constructions for these and related problems. [ABSTRACT FROM AUTHOR]

In the ElGamal signature and encryption schemes, an element x of the underlying group G = Z p × = { 1 , ... , p − 1 } for a prime p is also considered as an exponent, for example in gx, where g is a generator of G. This ElGamal map x ↦ g x is poorly understood, and one may wonder whether it has some randomness properties. This work presents two pieces of evidence for randomness. Firstly, experiments with small primes suggest that the map behaves like a uniformly random permutation with respect to two properties that we consider. Secondly, the theory of Sidon sets shows that the graph of this map is equidistributed in a suitable sense. It remains an open question to prove more randomness properties, for example, that the ElGamal map is pseudorandom. [ABSTRACT FROM AUTHOR]

Let S⊆N be a numerical semigroup with multiplicity m, conductor c and minimal generating set P. Let L=S∩[0,c-1] and W(S)=|P||L|-c. In 1978, Herbert Wilf asked whether W(S)≥0 always holds, a question known as Wilf's conjecture and open since then. A related number W0(S), satisfying W0(S)≤W(S), has recently been introduced. We say that S is a near-miss in Wilf's conjecture if W0(S)<0. Near-misses are very rare. Here we construct infinite families of them, with c=4m and W0(S) arbitrarily small, and we show that the members of these families still satisfy Wilf's conjecture. [ABSTRACT FROM AUTHOR]

Let G be a finite abelian group, and let r be a multiple of its exponent. The generalized Erdős--Ginzburg--Ziv constant sr(G) is the smallest integer s such that every sequence of length s over G has a zero-sum subsequence of length r. We show that s2m(Z2d) ≤ Cm2d/m + O(1) when d →∞, and s2m(Z2d) ≥ 2d/m + 2m - 1 when d = km. We use results on sr(G) to prove new bounds for the codegree Turán density of complete r-graphs. [ABSTRACT FROM AUTHOR]

A (tandem) duplication of length ${k} $ is an insertion of an exact copy of a substring of length ${k} $ next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshtein’s construction of binary codes correcting insertions of zeros is, with minor modifications, applicable also to channels with arbitrary alphabets and withduplicationerrors of arbitrary (but fixed) length ${k} $. Furthermore, we derive bounds on the cardinality of optimal ${q} $ -ary codes correcting up to ${t} $ duplications of length ${k} $ and establish the following corollaries in the asymptotic regime of growing block length: 1) the presented family of codes is optimal for every ${q, t, k} $ , in the sense of the asymptotic scaling of code redundancy; 2) the upper bound, when specialized to ${q=2} $ , ${k=1} $ , improves upon Levenshtein’s bound for every ${t\geq 3} $ ; and 3) the bounds coincide for ${t=1} $ , thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes. [ABSTRACT FROM AUTHOR]

A sequence in a C∗-algebra A is called completely Sidon if its span in A is completely isomorphic to the operator space version of the space ℓ1 (i.e. ℓ1 equipped with its maximal operator space structure). The latter can also be described as the span of the free unitary generators in the (full) C∗-algebra of the free group F∞ with countably infinitely many generators. Our main result is a generalization to this context of Drury’s classical theorem stating that Sidon sets are stable under finite unions. In the particular case when A=C∗(G) the (maximal) C∗-algebra of a discrete group G, we recover the non-commutative (operator space) version of Drury’s theorem that we recently proved. We also give several non-commutative generalizations of our recent work on uniformly bounded orthonormal systems to the case of von Neumann algebras equipped with normal faithful tracial states. [ABSTRACT FROM AUTHOR]

We extend to metrizable locally compact groups Rosenthal's theorem describing those Banach spaces containing no copy of ℓ 1 . For that purpose, we transfer to general locally compact groups the notion of interpolation ( I 0 ) set, which was defined by Hartman and Ryll-Nardzewsky [24] for locally compact abelian groups. Thus we prove that for every sequence { g n } n < ω in a locally compact group G , then either { g n } n < ω has a weak Cauchy subsequence or contains a subsequence that is an I 0 set. This result is subsequently applied to obtain sufficient conditions for the existence of Sidon sets in a locally compact group G , an old question that remains open since 1974 (see [31] and [19] ). Finally, we show that every locally compact group strongly respects compactness extending thereby a result by Comfort, Trigos-Arrieta, and Wu [13] , who established this property for abelian locally compact groups. [ABSTRACT FROM AUTHOR]

Motivated by communication channels in which the transmitted sequences are subjected to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaired by insertions, deletions, substitutions, and erasures of symbols. Several constructions of error-correcting codes for this channel are described, and bounds on the size of optimal codes correcting any given number of errors are derived. The construction based on the notion of Sidon sets in finite Abelian groups is shown to be optimal, in the sense of the asymptotic scaling of code redundancy, for any error radius and alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases. [ABSTRACT FROM AUTHOR]

For a subset A ⊆ [ N ] , we define the representation function r A − A ( d ) : = # { ( a , a ′ ) ∈ A × A : d = a − a ′ } and define M D ( A ) : = max 1 ≤ d < D ⁡ r A − A ( d ) for D > 1 . We study the smallest possible value of M D ( A ) as A ranges over all possible subsets of [ N ] with a given size. We give explicit asymptotic expressions with constant coefficients determined for a large range of D . We shall also see how this problem connects to a well-known problem about generalized Sidon sets. [ABSTRACT FROM AUTHOR]

A set S of natural numbers is a Sidon set if all the sums s1 +s2 with s1, s2 2 S and s1 s2 are distinct. Let constant > 0 and 0 << 1 be xed, and let pm = minf1;m1+g for all positive integers m. Generate a random set R N by adding m to R with probability pm, independently for each m. We investigate how dense a Sidon set S contained in R can be. Our results show that the answer is qualitatively very diferent in at least three ranges of . We prove quite accurate results for the range 0 < 2=3, but only obtain partial 1. [ABSTRACT FROM AUTHOR]

A Bh set (or Sidon set of order h) in an Abelian group G is any subset {b0,b1,...,bn} of G with the property that all the sums bi1 +⋯+bih are different up to the order of the summands. Let ø(h, n) denote the order of the smallest Abelian group containing a Bh set of cardinality n+1. It is shown that limh→∞ ø(h,n)/hn= 1/n! δL(Δn), where δL(Δn) is the lattice packing density of an n-simplex in Euclidean space. This determines the asymptotics exactly in cases where this density is known (n ≤ 3) and gives improved bounds on ø(h, n) in the remaining cases. The corresponding geometric characterization of bases of order h in finite Abelian groups in terms of lattice coverings by simplices is also given. [ABSTRACT FROM AUTHOR]

We prove that every infinite, discrete abelian group admits a pair of I0 sets whose union is not I0. In particular, this implies that every such group contains a Sidon set that is not I0. [ABSTRACT FROM AUTHOR]

We prove that every infinite, discrete abelian group admits a pair of I0 sets whose union is not I0. In particular, this implies that every such group contains a Sidon set that is not I0. [ABSTRACT FROM AUTHOR]

For n ∈ ℤ and A ⊆ ℤ, define rA(n) and δA(n) by rA(n) = #{(a1, a2) ∈ A2: n = a1 + a2, a1 ≤ a2} and δA(n) = #{(a1, a2) ∈ A2 : n = a1 - a2}. We call A a unique representation bi-basis if rA(n) = 1 for all n ∈ ℤ and δA(n) = 1 for all n ∈ ℤ\{0}. In this paper, we prove that there exists a unique representation bi-basis A such that lim supx→∞ A(-x, x)= √x ≥ 1/√2. [ABSTRACT FROM AUTHOR]

A set S of integers is a B 3 -set if all the sums of the form a 1 + a 2 + a 3 , with a 1 , a 2 and a 3 ∈ S and a 1 ≤ a 2 ≤ a 3 , are distinct. We obtain asymptotic bounds for the number of B 3 -sets of a given cardinality contained in the interval [ n ] = { 1 , … , n } . We use these results to estimate the maximum size of a B 3 -set contained in a typical (random) subset of [ n ] of a given cardinality. These results confirm conjectures recently put forward by the authors [ On the number of B h -sets , Combin. Probab. Comput. 25 (2016), no. 1, 108–127]. [ABSTRACT FROM AUTHOR]

Let and be infinite sequences of nonnegative integers. For a positive integer let denote the number of representations of as the sum of two terms from . Let denote the maximum value of up to and denote the distance of the sequences and . In this paper, we study the connection between , and . We improve a result of Haddad and Helou about the Erdős-Turán conjecture. [ABSTRACT FROM AUTHOR]

Let 풜 = {a1 < a2 < a3 < ⋯ < an < ⋯} be an infinite sequence of nonnegative integers and let R2(n) = |{(i, j) : ai + aj = n; ai, aj ∈ 풜; i ≤ j}|. We define . We prove that if the L∞-norm of is small, then the L1-norm of is large. [ABSTRACT FROM AUTHOR]

Abstract: We present a unified framework to deal with threshold functions for the existence of certain combinatorial structures in random sets. More precisely, let be a linear system defining a fixed structure (k-arithmetic progressions, k-sums, sets or Hilbert cubes, for example), and be a random set on where each element is chosen independently with the same probability. We show that, under certain natural conditions, there exists a threshold function for the property “ contains a non-trivial solution of ” which only depends on the dimensions of M. We study the behavior of the limiting distribution of the number of non-trivial solutions in the threshold scale, and show that it follows a Poisson distribution in terms of volumes of certain convex polytopes arising from the linear system under study. [Copyright &y& Elsevier]