Generalized Sidon sets

We give asymptotic sharp estimates for the cardinality of a set of residue classes with the property that the representation function is bounded by a prescribed number. We then use this to obtain an analogous result for sets of integers, answering an old question of Simon Sidon.     

On generalized perfect difference sets constructed from Sidon sets

Let $\mathbb{N}$ be the set of positive integers. For a nonempty set A of integers and every integer u, denote by $d_A(u)$ the number of $(a,a^{\prime })$ with $a,a^{\prime }\in A$ such that $u=a-a^{\prime }$. For a sequence S of positive integers, let $S(x)$ be the counting function of S. The set $A\subseteq \mathbb{N}$ is called a perfect difference set if $d_A(u)=1$ for every positive integer u. In 2008, Cilleruelo and Nathanson (2008) [4] constructed dense perfect difference sets from dense Sidon sets. In this paper, as a main result, we prove that: let $f:\mathbb{N}\to \mathbb{N}$ be an increasing function satisfying $f(n)\ge 2$ for any positive integer n, then for every Sidon set B and every function $\omega (x)\to \infty$, there exists a set $A\subseteq \mathbb{N}$ such that $d_A(u)=f(u)$ for every positive integer u and $B(x/3)-\omega (x)\le A(x)\le B(x/3)+\omega (x)$ for all $x\ge C_{f,B,\omega }$.     

Generalized perfect arrays and menon difference sets

Given an s ₁ × ... × s _rinteger-valued array A and a (0, 1) vector z = (z ₁, ..., z _r), form the array A from A by recursively adjoining a negative copy of the current array for each dimension i where z _i = 1. A is a generalized perfect array type z if all periodic autocorrelation coefficients of A are zero, except for shifts (u ₁, ..., u _r) where u _i, - 0 (mod s _i) for all i. The array is perfect if z = (0, ..., 0) and binary if the array elements are all ±1. A nontrivial perfect binary array (PBA) is equivalent to a Menon difference set in an abelian group.Using only elementary techniques, we prove various construction theorems for generalized perfect arrays and establish conditions on their existence. We show that a generalized PBA whose type is not (0, ..., 0) is equivalent to a relative difference set in an abelian factor group. We recursively construct several infinite families of generalized PBAs, and deduce nonexistence results for generalized PBAs whose type is not (0, ..., 0) from well-known nonexistence results for PBAs. A central result is that a PBA with 2^2y 3^2u elements and no dimension divisible by 9 exists if and only if no dimension is divisible by 2 ^y+2. The results presented here include and enlarge the set of sizes of all previously known generalized PBAs.     

Perfect difference sets constructed from Sidon sets

A set of positive integers is a perfect difference set if every nonzero integer has a unique representation as the difference of two elements of . We construct dense perfect difference sets from dense Sidon sets. As a consequence of this new approach we prove that there exists a perfect difference set such that

Constructions of generalized Sidon sets

We give explicit constructions of sets S with the property that for each integer k, there are at most g solutions to k=s₁+s₂,s_i∈S; such sets are called Sidon sets if g=2 and generalized Sidon sets if g?3. We extend to generalized Sidon sets the Sidon-set constructions of Singer, Bose, and Ruzsa. We also further optimize Kolountzakis’ idea of interleaving several copies of a Sidon set, extending the improvements of Cilleruelo, Ruzsa and Trujillo, Jia, and Habsieger and Plagne. The resulting constructions yield the largest known generalized Sidon sets in virtually all cases.     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

Additive and multiplicative Sidon sets

Summary Inspired by a paper of Sárk?zy [4] we study sets of integers and sets of residues with the property that all sums and all products are distinct.     

Additive and multiplicative Sidon sets

Acta Mathematica Hungarica - We give a construction of a set $$A \subset \mathbb N$$ such that any subset $${A' \subset A}$$ with $$|A'| \gg |A|^{2/3}$$ is neither an additive nor...     

On the structure of Sidon sets

LetG be any connected compact group with dual object. We give in this paper a new proof that the union of any two Sidon sets in is again a Sidon set. We also show that any Sidon subset of is the union of a set whose elements have bounded degree with a finite union of sets which satisfy a quasi-independence condition.     

On Sidon sets which are asymptotic bases

Let h ≧ 2 be an integer. We say that a set $ \mathcal{A} $ of positive integers is an asymptotic basis of order h if every large enough positive integer can be represented as the sum of h terms from $ \mathcal{A} $ . A set of positive integers $ \mathcal{A} $ is called a Sidon set if all the sums a + b with $ a \in \mathcal{A},b \in \mathcal{A},a \leqq b $ , are distinct. In this paper we prove the existence of Sidon sets which are asymptotic bases of order 5 by using probabilistic methods.     

The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers

A set A of non‐negative integers is called a Sidon set if all the sums , with and a₁, , are distinct. A well‐known problem on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of . Results of Chowla, Erd?s, Singer and Turán from the 1940s give that . We study Sidon subsets of sparse random sets of integers, replacing the ‘dense environment’ by a sparse, random subset R of , and ask how large a subset can be, if we require that S should be a Sidon set. Let be a random subset of of cardinality , with all the subsets of equiprobable. We investigate the random variable , where the maximum is taken over all Sidon subsets , and obtain quite precise information on for the whole range of m, as illustrated by the following abridged version of our results. Let be a fixed constant and suppose . We show that there is a constant such that, almost surely, we have . As it turns out, the function is a continuous, piecewise linear function of a that is non‐differentiable at two ‘critical’ points: a = 1/3 and a = 2/3. Somewhat surprisingly, between those two points, the function is constant. Our approach is based on estimating the number of Sidon sets of a given cardinality contained in [n]. Our estimates also directly address a problem raised by Cameron and Erd?s (On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), de Gruyter, Berlin, 1990, pp. 61–79). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 1–25, 2015     

Combinatorial problems in finite fields and Sidon sets

We use Sidon sets to present an elementary method to study some combinatorial problems in finite fields, such as sum product estimates, solvability of some equations and the distribution of their solutions. We obtain classic and more recent results avoiding the use of exponential sums, the usual tool to deal with these problems.     

A note on the growth of topological Sidon sets

We give an estimate for the number of elements in the intersection of topological Sidon sets inR ⁿ with compact convex subsets and deduce a necessary and sufficient conditions for an orbit of a linear transformation ofR ⁿ to be a topological Sidon set.     

Tabular powers of maximal sets

The following result is established for reducibility of tabular type. Whatever the recursively enumerated nonrecursive incomplete power is, there exists a power, not congruent with it, containing a maximal set.Translated from Matematicheskie Zametki, Vol. 20, No. 3, pp. 373–381, September, 1976.     

Generalized perfect spaces

Given two Banach function spaces X and Y related to a measure μ, the Y-dual space X^Y of X is defined as the space of the multipliers from X to Y. The space X^Y is a generalization of the classical Köthe dual space of X, which is obtained by taking Y = L^t(μ). Under minimal conditions, we can consider the Y-bidual space X^YY of X (i.e. the Y-dual of X^Y). As in the classical case, the containment X ⊂ X^YY always holds. We give conditions guaranteeing that X coincides with X^YY, in which case X is said to be Y-perfect. We also study when X is isometrically embedded in X^YY. Properties involving p-convexity, p-concavity and the order of X and Y, will have a special relevance.     

Detecting perfect powers by factoring into coprimes

This paper presents an algorithm that, given an integer , finds the largest integer such that is a th power. A previous algorithm by the first author took time where ; more precisely, time ; conjecturally, time . The new algorithm takes time . It relies on relatively complicated subroutines--specifically, on the first author's fast algorithm to factor integers into coprimes--but it allows a proof of the bound without much background; the previous proof of relied on transcendental number theory.

The computation of is the first step, and occasionally the bottleneck, in many number-theoretic algorithms: the Agrawal-Kayal-Saxena primality test, for example, and the number-field sieve for integer factorization.