Cameron and Erd\H{o}s asked if the number of sets free of arithmetic progressions of length $k$ is $2^{r_k(n)(1+o(1))}$, where $r_k(n)$ is the maximum cardinality of a $k$-AP-free subset of $\{1, \dots, n\}$. Balogh, Liu and Sharifzadeh made significant progress on this question showing that it is $2^{O(r_k(n))}$ for an infinite sequence of $n$. We improve their result in two ways. On the one hand, we prove that, for $k\geq 5$, the number of $k$-AP-free sets in $[n]$ is $2^{r_k(n)(1+o(1))}$ for an infinite sequence of $n$, solving the question of Cameron and Erd\H{o}s for infinitely many values. On the other hand, we also prove that for $k \geq 3$ and all $n$ the number of $k$-AP-free sets in $[n]$ is $2^{O(r_k(n))}$. These results are in fact special cases of a general framework that we develop to count families of sets excluding certain arithmetic patterns, which applies as long as the corresponding extremal threshold satisfies certain Behrend-type lower bounds. As further examples, we get analogous results for solution sets to almost all systems of linear equations as well as counting versions of the multidimensional Szemer\'edi theorem.
For integers $r\ge2$ and $n\ge1$, let $$ F_{r,n}(q)=\prod_{k=1}^{n}\frac{1-q^{rk}}{1-q^k}. $$ The coefficient of $q^j$ in \(F_{r,n}(q)\) counts partitions of $j$ into parts at most $n$, each occurring at most $r-1$ times. Hughes proved that $F_{2,n}(q)=\prod_{k=1}^{n}(1+q^k)$ is unimodal for every $n\ge 1$. This result...
Let $d$ be the divisor function, and let $K(n)$ be the least positive integer $K$ for which $d((n + K)!) \ge 2d(n!)$. Erd\H{o}s, Graham, Ivi\'c and Pomerance proved that, for infinitely many $n$, \begin{equation*} K(n)>(1/9)(\log n)(\log_{2} n)(\log_{4} n)/(\log_{3} n)^3. \end{equation*} We improve upon this by a facto...
A subset of the $d$-dimensional lattice cube $[n]^d$ is sum-free if it contains no solution to the equation $x+y=z$. We study the total number of such subsets. For $d=1$, Cameron and Erd\H{o}s conjectured that the number of sum-free subsets of $[n]$ is $O(2^{n/2})$, and this was proved independently by Green and Sapozh...
For practical $N$ let $h(N)$ be the least $k$ such that every integer $1\le m\le N$ is a sum of at most $k$ distinct divisors of $N$. We prove $h(n!)\le(2\log2+o(1))\,n/\log n$. This improves the bounds of order $n/(\log n)^{1/2-\varepsilon}$ established in Tenenbaum-Yokota's Lemma 4 and Yokota's 1995 knapsack note. We...
A family of subsets of $[n]$ is $r$-fork-free if none of its members is strictly contained in $r$ other distinct members. For each fixed integer $r\ge2$, we prove that the maximum size of such a family is \[ \binom{n}{\lfloor n/2\rfloor} \left(1+\frac{2(r-1)}{n}+o(n^{-1})\right). \] This determines the second-order ter...
Following Erd\H{o}s (1982) and Sanna (2019), we study the arithmetic function $h(n)$, which is defined to be the number of distinct exponents in the prime factorization of a positive integer $n$. Among other things, we show that $$ \sum_{n\leq x}h(\phi(n)) \asymp x\left(\frac{\log\log x}{\log\log\log x}\right)^{1/2}, $...
Mikhail R. Gabdullin, V. V. Iudelevich· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
