词条 | Behrend's theorem |
释义 |
In arithmetic combinatorics, Behrend's theorem states that the subsets of the integers from 1 to in which no member of the set is a multiple of any other must have a logarithmic density that goes to zero as becomes large. The theorem is named after Felix Behrend, who published it in 1935. StatementThe logarithmic density of a set of integers from 1 to can be defined by setting the weight of each integer to be , and dividing the total weight of the set by (or, equivalently for the purposes of asymptotic analysis, dividing by the th partial sum of the harmonic series). The resulting number is 1 or close to 1 when the set includes all of the integers in that range, but smaller when many integers are missing, and particularly when the missing integers are themselves small.{{r|s13}} A subset of is called primitive if it has the property that no subset element is a multiple of any other element. Behrend's theorem states that the logarithmic density of any primitive subset must be small. More precisely, the logarithmic density of such a set must be .{{r|s13}} For infinite primitive sequences, the maximum possible density is smaller, .{{r|ess67a}} ExamplesThere exist large primitive subsets of . However, these sets still have small logarithmic density.
Both of these subsets have significantly smaller logarithmic density than the bound given by Behrend's theorem. Resolving a conjecture of G. H. Hardy, both Paul Erdős and Subbayya Sivasankaranarayana Pillai showed that, for , the set of numbers with exactly prime factors (counted with multiplicity) has logarithmic density exactly matching the form of Behrend's theorem.{{r|e48}} This example is best possible, in the sense that no other primitive subset has logarithmic density with the same form and a larger leading constant.{{r|ess67b}} HistoryThis theorem is known as Behrend's theorem because Felix Behrend proved it in 1934,{{r|s13}} and published it in 1935.{{r|b35}} Paul Erdős proved the same result, on a train ride in 1934 in which he traveled from Hungary to Cambridge to escape the growing anti-semitism of Europe at that time, but on his arrival he discovered that Behrend's proof was already known.{{r|s13}} References1. ^{{citation | last = Erdős | first = P. | authorlink = Erdős | doi = 10.2307/1969113 | journal = Annals of Mathematics | mr = 0023279 | pages = 53–66 | series = Second Series | title = On the integers having exactly prime factors | url = https://users.renyi.hu/~p_erdos/1948-08.pdf | volume = 49 | year = 1948}} [1][2][3][4]2. ^{{citation | last1 = Erdős | first1 = P. | author1-link = Erdős | last2 = Sárközy | first2 = A. | author2-link = András Sárközy | last3 = Szemerédi | first3 = E. | author3-link = Endre Szemerédi | journal = Journal of the Australian Mathematical Society | mr = 0209246 | pages = 9–16 | title = On a theorem of Behrend | url = https://users.renyi.hu/~p_erdos/1967-09.pdf | volume = 7 | year = 1967}} 3. ^{{citation | last1 = Erdős | first1 = P. | author1-link = Erdős | last2 = Sárközy | first2 = A. | author2-link = András Sárközy | last3 = Szemerédi | first3 = E. | author3-link = Endre Szemerédi | doi = 10.1112/jlms/s1-42.1.484 | journal = Journal of the London Mathematical Society | mr = 0218325 | pages = 484–488 | series = Second Series | title = On an extremal problem concerning primitive sequences | url = https://users.renyi.hu/~p_erdos/1967-10.pdf | volume = 42 | year = 1967}} 4. ^{{citation | last = Sárközy | first = A. | authorlink = András Sárközy | editor1-last = Graham | editor1-first = Ronald L. | editor1-link = Ronald Graham | editor2-last = Nešetřil | editor2-first = Jaroslav | editor2-link = Jaroslav Nešetřil | contribution = On divisibility properties of sequences of integers | doi = 10.1007/978-3-642-60408-9_19 | edition = 2nd | location = Berlin | mr = 1425189 | pages = 221–232 | publisher = Springer | series = Algorithms and Combinatorics | title = The mathematics of Paul Erdős, I | volume = 13 | year = 2013}}. See in particular [https://books.google.com/books?id=onG8BAAAQBAJ&pg=PA222 p. 222]. }} 1 : Theorems in number theory |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。