ON PARTITIONING SIDON SETS WITH QUASI-INDEPENDENT SETS BY

Sidon subsets have been characterized by Pisier as having proportional quasi-independent subsets [8]. There remains the open problem of whether Sidon subsets of Zmust be finite unions of quasi-independent sets. Grow and Whicher produced an interesting example of a Sidon set whose Pisier pro-portionality was 1/2 but the set was not the union of two quasi-independent sets [3]. On the other hand, the present paper provides probabilistic evi-dence in favor of an affirmative answer with a construction of random Sidon sets which borrows heavily from ideas of Professors Katznelson and Mallia-vin [6, 4, 5]. Katznelson provided a random construction of integer Sidon sets which, almost surely, were not dense in the Bohr compactifaction of the integers [4, 5]. This paper presents a modification of that construction and emphasizes a stronger conclusion which is implicit in the earlier construc-tion: almost surely, the random sets are finite unions of quasi-independent sets (also of N-independent sets, defined below). In this paper, random subsets of size O(log nj) are chosen from disjoint arithmetic progressions of length nj (the maximum density allowed for a Sidon set), with nj → ∞ fast enough and the progressions rapidly dilated as j →∞. This paper concludes with several deterministic results. If every Sidon subset of Z\{0} is a finite union of quasi-independent sets, then the required number of quasi-independent sets is bounded by a function of the Sidon constant. Analogs of this result are proved for all Abelian groups, and for other special Sidon sets (the N-independent sets). Throughout this paper, unspecified variables denote positive integers. Definition. A subset F ⊂ Z is said to be N-independent if and only if, for all integers αx ∈ [−N,N], with αx 6 = 0 for at most finitely many x