The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers1. Issue 1 (3rd April 2013)

• Record Type: Journal Article
• Authors: Kohayakawa, Yoshiharu; Lee, Sang June; Rödl, Vojtěch; Samotij, Wojciech
• Is Part Of: Random structures & algorithms. Volume 46:Issue 1(2015)
• Page Start: 1
• Page End: 25
• Publication Date: 2013-04-03
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20496
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>A set <italic>A</italic> of non‐negative integers is called a <italic>Sidon set</italic> if all the sums <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbbx4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>a</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>+</mml:mo><mml:msub><mml:mi>a</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></alternatives></inline-formula>, with <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbc2v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>a</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>≤</mml:mo><mml:msub><mml:mi>a</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></alternatives></inline-formula> and <italic>a</italic><sub>1</sub>, <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbbqt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>a</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>∈</mml:mo><mml:mi>A</mml:mi></mml:mrow></mml:math></alternatives></inline-formula>, are distinct. A well‐known problem on Sidon sets is the determination of the maximum possible size <italic>F</italic>(<italic>n</italic>) of a Sidon subset of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbbwk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo><mml:mo>=</mml:mo><mml:mo>{</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo>, </mml:mo><mml:mo>…</mml:mo><mml:mo>, </mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>}</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. Results of Chowla, Erdős, Singer and Turán from the 1940s give that <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbcrw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>F</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:msqrt><mml:mi>n</mml:mi></mml:msqrt></mml:mrow></mml:math></alternatives></inline-formula>. We study Sidon subsets of sparse random sets of integers, replacing the 'dense environment' <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbck4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> by a sparse, random subset <italic>R</italic> of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbcjk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, and ask how large a subset <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbcct" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>S</mml:mi><mml:mo>⊂</mml:mo><mml:mi>R</mml:mi></mml:mrow></mml:math></alternatives></inline-formula> can be, if we require that <italic>S</italic> should be a Sidon set. Let <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbcw3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>R</mml:mi><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:mi>m</mml:mi></mml:msub></mml:mrow></mml:math></alternatives></inline-formula> be a random subset of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbd1t" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> of cardinality <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbd3x" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, with all the <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbd51" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>m</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives></inline-formula> subsets of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbd97" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> equiprobable. We investigate the random variable <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbddw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0014" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>F</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:mi>m</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>max</mml:mi><mml:mo>|</mml:mo><mml:mi>S</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, where the maximum is taken over all Sidon subsets <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbdff" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0015" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>S</mml:mi><mml:mo>⊂</mml:mo><mml:msub><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:mi>m</mml:mi></mml:msub></mml:mrow></mml:math></alternatives></inline-formula>, and obtain quite precise information on <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbdzq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0016" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>F</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:mi>m</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> for the whole range of <italic>m</italic>, as illustrated by the following abridged version of our results. Let <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbdsz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0017" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>0</mml:mn><mml:mo>≤</mml:mo><mml:mi>a</mml:mi><mml:mo>≤</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> be a fixed constant and suppose <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbf63" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0018" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mi>a</mml:mi></mml:msup></mml:mrow></mml:math></alternatives></inline-formula>. We show that there is a constant <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbf1b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0019" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>b</mml:mi><mml:mo>=</mml:mo><mml:mi>b</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>a</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> such that, almost surely, we have <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbg1v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0020" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>F</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:mi>m</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mi>b</mml:mi><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup></mml:mrow></mml:math></alternatives></inline-formula>. As it turns out, the function <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbfrx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0021" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>b</mml:mi><mml:mo>=</mml:mo><mml:mi>b</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>a</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> is a continuous, piecewise linear function of <italic>a</italic> that is non‐differentiable at two 'critical' points: <italic>a</italic> = 1/3 and <italic>a</italic> = 2/3. Somewhat surprisingly, between those two points, the function <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbft1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20496:rsa20496-math-0022" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>b</mml:mi><mml:mo>=</mml:mo><mml:mi>b</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>a</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> is constant.</p> <p>Our approach is based on estimating the number of Sidon sets of a given cardinality contained in [<italic>n</italic>]. 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</p> </abstract>