共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
《Discrete Mathematics》2021,344(12):112589
Let be the set of positive integers. For a nonempty set A of integers and every integer u, denote by the number of with such that . For a sequence S of positive integers, let be the counting function of S. The set is called a perfect difference set if 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 be an increasing function satisfying for any positive integer n, then for every Sidon set B and every function , there exists a set such that for every positive integer u and for all . 相似文献
3.
Generalized perfect arrays and menon difference sets 总被引:1,自引:0,他引:1
Jonathan Jedwab 《Designs, Codes and Cryptography》1992,2(1):19-68
Given an s
1 × ... × s
rinteger-valued array A and a (0, 1) vector z = (z
1, ..., 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
1, ..., 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 22y
32u
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. 相似文献
4.
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
.
Also we prove that there exists a perfect difference set
such that
A(x)/≥ 1/.
The work of J. C. was supported by Grant MTM 2005-04730 of MYCIT (Spain).
The work of M. B. N. was supported in part by grants from the NSA Mathematical Sciences Program and the PSC-CUNY Research
Award Program. 相似文献
5.
Greg Martin 《Journal of Combinatorial Theory, Series A》2006,113(4):591-607
We give explicit constructions of sets S with the property that for each integer k, there are at most g solutions to k=s1+s2,si∈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. 相似文献
6.
J.A. Dias da Silva 《Discrete Mathematics》2009,309(13):4489-4494
A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(ai,mi):i∈I} and {(bj,nj):j∈J} are multisets of size h with elements in X and ∑i∈Imiai=∑j∈Jnjbj, then {(ai,mi):i∈I}={(bj,nj):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. 相似文献
8.
9.
Imre Z. Ruzsa 《Acta Mathematica Hungarica》2006,112(4):345-354
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. 相似文献
10.
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... 相似文献
11.
David C. Wilson 《Monatshefte für Mathematik》1986,101(1):67-74
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. 相似文献
12.
S. Z. Kiss 《Acta Mathematica Hungarica》2010,128(1-2):46-58
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. 相似文献
13.
Colin C. Graham 《Arkiv f?r Matematik》1981,19(1-2):217-221
14.
15.
The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
下载免费PDF全文
![点击此处可从《Random Structures and Algorithms》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Yoshiharu Kohayakawa Sang June Lee Vojtěch Rödl Wojciech Samotij 《Random Structures and Algorithms》2015,46(1):1-25
A set A of non‐negative integers is called a Sidon set if all the sums , with and a1, , 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 相似文献
16.
Javier Cilleruelo 《Combinatorica》2012,32(5):497-511
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. 相似文献
17.
K. Gowri Navada 《Proceedings Mathematical Sciences》1995,105(3):281-285
We give an estimate for the number of elements in the intersection of topological Sidon sets inR
n with compact convex subsets and deduce a necessary and sufficient conditions for an orbit of a linear transformation ofR
n to be a topological Sidon set. 相似文献
18.
S. S. Marchenkov 《Mathematical Notes》1976,20(3):766-770
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. 相似文献
19.
Given two Banach function spaces X and Y related to a measure μ, the Y-dual space XY of X is defined as the space of the multipliers from X to Y. The space XY is a generalization of the classical Köthe dual space of X, which is obtained by taking Y = Lt(μ). Under minimal conditions, we can consider the Y-bidual space XYY of X (i.e. the Y-dual of XY). As in the classical case, the containment X ⊂ XYY always holds. We give conditions guaranteeing that X coincides with XYY, in which case X is said to be Y-perfect. We also study when X is isometrically embedded in XYY. Properties involving p-convexity, p-concavity and the order of X and Y, will have a special relevance. 相似文献
20.
Daniel J. Bernstein Hendrik W. Lenstra Jr. Jonathan Pila. 《Mathematics of Computation》2007,76(257):385-388
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.