Equal sums in random sets and the concentration of divisors
We study the extent to which divisors of a typical integer n are concentrated. In particular, defining Δ(𝑛):=max𝑡#{𝑑|𝑛,log𝑑∈[𝑡,𝑡+1]}, we show that Δ(𝑛)⩾(loglog𝑛)0.35332277… for almost all n, a bound we believe to be sharp. This disproves a conjecture of Maier and Tenenbaum. We also prove analogs for...
| Auteurs principaux: | , , |
|---|---|
| Format: | Journal article |
| Langue: | English |
| Publié: |
Springer
2023
|
| _version_ | 1826310833255219200 |
|---|---|
| author | Ford, K Green, B Koukoulopoulos, D |
| author_facet | Ford, K Green, B Koukoulopoulos, D |
| author_sort | Ford, K |
| collection | OXFORD |
| description | We study the extent to which divisors of a typical integer n are concentrated. In particular, defining Δ(𝑛):=max𝑡#{𝑑|𝑛,log𝑑∈[𝑡,𝑡+1]}, we show that Δ(𝑛)⩾(loglog𝑛)0.35332277… for almost all n, a bound we believe to be sharp. This disproves a conjecture of Maier and Tenenbaum. We also prove analogs for the concentration of divisors of a random permutation and of a random polynomial over a finite field. Most of the paper is devoted to a study of the following much more combinatorial problem of independent interest. Pick a random set 𝐀⊂ℕ by selecting i to lie in 𝐀 with probability 1/i. What is the supremum of all exponents 𝛽𝑘 such that, almost surely as 𝐷→∞, some integer is the sum of elements of 𝐀∩[𝐷𝛽𝑘,𝐷] in k different ways? We characterise 𝛽𝑘 as the solution to a certain optimisation problem over measures on the discrete cube {0,1}𝑘, and obtain lower bounds for 𝛽𝑘 which we believe to be asymptotically sharp. |
| first_indexed | 2024-03-07T07:57:51Z |
| format | Journal article |
| id | oxford-uuid:a97b03d7-7222-48c4-a7ed-9bd73b5bc0a2 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:57:51Z |
| publishDate | 2023 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:a97b03d7-7222-48c4-a7ed-9bd73b5bc0a22023-09-04T09:00:23ZEqual sums in random sets and the concentration of divisorsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:a97b03d7-7222-48c4-a7ed-9bd73b5bc0a2EnglishSymplectic ElementsSpringer2023Ford, KGreen, BKoukoulopoulos, DWe study the extent to which divisors of a typical integer n are concentrated. In particular, defining Δ(𝑛):=max𝑡#{𝑑|𝑛,log𝑑∈[𝑡,𝑡+1]}, we show that Δ(𝑛)⩾(loglog𝑛)0.35332277… for almost all n, a bound we believe to be sharp. This disproves a conjecture of Maier and Tenenbaum. We also prove analogs for the concentration of divisors of a random permutation and of a random polynomial over a finite field. Most of the paper is devoted to a study of the following much more combinatorial problem of independent interest. Pick a random set 𝐀⊂ℕ by selecting i to lie in 𝐀 with probability 1/i. What is the supremum of all exponents 𝛽𝑘 such that, almost surely as 𝐷→∞, some integer is the sum of elements of 𝐀∩[𝐷𝛽𝑘,𝐷] in k different ways? We characterise 𝛽𝑘 as the solution to a certain optimisation problem over measures on the discrete cube {0,1}𝑘, and obtain lower bounds for 𝛽𝑘 which we believe to be asymptotically sharp. |
| spellingShingle | Ford, K Green, B Koukoulopoulos, D Equal sums in random sets and the concentration of divisors |
| title | Equal sums in random sets and the concentration of divisors |
| title_full | Equal sums in random sets and the concentration of divisors |
| title_fullStr | Equal sums in random sets and the concentration of divisors |
| title_full_unstemmed | Equal sums in random sets and the concentration of divisors |
| title_short | Equal sums in random sets and the concentration of divisors |
| title_sort | equal sums in random sets and the concentration of divisors |
| work_keys_str_mv | AT fordk equalsumsinrandomsetsandtheconcentrationofdivisors AT greenb equalsumsinrandomsetsandtheconcentrationofdivisors AT koukoulopoulosd equalsumsinrandomsetsandtheconcentrationofdivisors |