Search

Erdős proved that F ( A ) : = ∑ a ∈ A 1 a log ⁡ a converges for any primitive set of integers A and later conjectured this sum is maximized when A is the set of primes. Banks and Martin further conjectured that F ( P 1 ) > ⋯ > F ( P k ) > F ( P k + 1 ) > ⋯ , where P j is the set of integers with j prime factors counting multiplicity, though this was recently disproven by Lichtman. We consider the corresponding problems over the function field F q [ x ] , investigating the sum F ( A ) : = ∑ f ∈ A 1 deg f ⋅ q deg f . We establish a uniform bound for F ( A ) over all primitive sets of polynomials A ⊂ F q [ x ] and conjecture that it is maximized by the set of monic irreducible polynomials. We find that the analogue of the Banks-Martin conjecture is false for q = 2 , 3, and 4, but we find computational evidence that it holds for q > 4 .

We prove the existence of primitive sets (sets of integers in which no element divides another) in which the gap between any two consecutive terms is substantially smaller than the best known upper bound for the gaps in the sequence of prime numbers. The proof uses the probabilistic method. Using the same techniques we improve the bounds obtained by He for gaps in geometric-progression-free sets., Comment: 10 pages, corrected proof of Theorem 2.2

Several recent papers have considered the Ramsey-theoretic problem of how large a subset of integers can be without containing any 3-term geometric progressions. This problem has also recently been generalized to number fields, determining bounds on the greatest possible density of ideals avoiding geometric progressions. We study the analogous problem over F q x , first constructing a set greedily which avoids these progressions and calculating its density, and then considering bounds on the upper density of subsets of F q x which avoid 3-term geometric progressions. This new setting gives us a parameter q to vary and study how our bounds converge to 1 as it changes, and positive characteristic introduces some extra combinatorial structure that increases the tractability of common questions in this area.

A partition $\alpha$ is said to contain another partition (or pattern) $\mu$ if the Ferrers board for $\mu$ is attainable from $\alpha$ under removal of rows and columns. We say $\alpha$ avoids $\mu$ if it does not contain $\mu$. In this paper we count the number of partitions of $n$ avoiding a fixed pattern $\mu$, in terms of generating functions and their asymptotic growth rates. We find that the generating function for this count is rational whenever $\mu$ is (rook equivalent to) a partition in which any two part sizes differ by at least two. In doing so, we find a surprising connection to metacyclic $p$-groups. We further obtain asymptotics for the number of partitions of $n$ avoiding a pattern $\mu$. Using these asymptotics we conclude that the generating function for $\mu$ is not algebraic whenever $\mu$ is rook equivalent to a partition with distinct parts whose first two parts are positive and differ by 1., Comment: 28 Pages, 1 table

Let Q ( n ) denote the count of the primitive subsets of the integers { 1 , 2 … , n } . We give a new proof that Q ( n ) = α ( 1 + o ( 1 ) ) n for some constant α , which allows us to give a good error term and to improve upon the lower bound for the value of α . We also show that the method developed can be applied to many similar problems related to the divisor graph, including other questions about primitive sets, geometric-progression-free sets, and the divisor graph path-cover problem.

We introduce a new arithmetic function $a(n)$ defined to be the number of random multiplications by residues modulo $n$ before the running product is congruent to 0 modulo $n$. We give several formulas for computing the values of this function and analyze its asymptotic behavior. We find that it is closely related to $P_1(n)$, the largest prime divisor of $n$. In particular, $a(n)$ and $P_1(n)$ have the same average order asymptotically. Furthermore, the difference between the functions $a(n)$ and $P_1(n)$ is $o(1)$ as $n$ tends to infinity on a set with density approximately $0.623$. On the other hand however, we see that (except on a set of density zero) the difference between $a(n)$ and $P_1(n)$ tends to infinity on the integers outside this set. Finally we consider the asymptotic behaviour of the difference between these two functions and find that $\sum_{n\leq x}\big( a(n)-P_1(n)\big) \sim \left(1-\frac{\pi}{4}\right)\sum_{n\leq x} P_2(n)$, where $P_2(n)$ is the second largest divisor of $n$.

We consider the distribution of the largest prime divisor of the integers in the interval [2, x] and investigate in particular the mode of this distribution, the prime number(s) which show up most often in this list. In addition to giving an asymptotic formula for this mode as x tends to infinity, we look at the set of those prime numbers which, for some value of x, occur most frequently as the largest prime divisor of the integers in the interval [2, x]. We find that many prime numbers never have this property. We compare the set of “popular primes,” those primes which are at some point the mode, to other interesting subsets of the prime numbers. Finally, we apply the techniques developed to a similar problem which arises in the analysis of factoring algorithms.

Let pn denote the n-th prime number, and consider the prime number graph, the collection of points (n, pn) in the plane. Pomerance uses the points lying on the boundary of the convex hull of this graph to show that there are infinitely many n such that p2n < pn−i + pn+i for all i < n. More recently, the primes on the boundary of this convex hull have been considered by Tutaj. We resolve several conjectures of Pomerance and Tutaj by giving improved bounds on the number and distribution of these primes as well as related forms of ‘extreme’ primes.

Two well-studied Ramsey-theoretic problems consider subsets of the natural numbers which either contain no three elements in arithmetic progression or in geometric progression. We study generalizations of this problem by varying the kinds of progressions to be avoided and the metrics used to evaluate the density of the resulting subsets. One can view a 3-term arithmetic progression as a sequence \(x, f_n(x), f_n(f_n(x))\), where \(f_n(x) = x + n\), n a nonzero integer. Thus, avoiding 3-term arithmetic progressions are equivalent to containing no three elements of the form \(x, f_n(x), f_n(f_n(x))\) with \(f_n \in \mathscr {F}_\mathrm{t}\), the set of integer translations. One can similarly construct related progressions using different families of functions. We investigate several such families, including geometric progressions (\(f_n(x) = nx\) with \(n > 1\) a natural number) and exponential progressions (\(f_n(x) = x^n\)). Progression-free sets are often constructed “greedily,” including every number so long as it is not in progression with any of the previous elements. Rankin characterized the greedy geometric-progression-free set in terms of the greedy arithmetic set. We characterize the greedy exponential set and prove that it has asymptotic density 1 and then discuss how the optimality of the greedy set depends on the family of functions used to define progressions. Traditionally, the size of a progression-free set is measured using the (upper) asymptotic density; however, we consider several different notions of density, including the uniform and exponential densities.

In this paper, we prove that there are infinitely many [Formula: see text]’s for which [Formula: see text] but [Formula: see text] is not a Carmichael number. Additionally, we prove that for any [Formula: see text], there exist infinitely many [Formula: see text]’s such that [Formula: see text] but [Formula: see text]. The constructions that we consider here are generalizations of Carmichael and Lehmer numbers, respectively, that were first formulated by Grau and Oller-Marcén.

The problem of looking for subsets of the natural numbers which contain no 3-term arithmetic progressions has a rich history. Roth's theorem famously shows that any such subset cannot have positive upper density. In contrast, Rankin in 1960 suggested looking at subsets without three-term geometric progressions, and constructed such a subset with density about 0.719. More recently, several authors have found upper bounds for the upper density of such sets. We significantly improve upon these bounds, and demonstrate a method of constructing sets with a greater upper density than Rankin's set. This construction is optimal in the sense that our method gives a way of effectively computing the greatest possible upper density of a geometric-progression-free set. We also show that geometric progressions in Z/nZ behave more like Roth's theorem in that one cannot take any fixed positive proportion of the integers modulo a sufficiently large value of n while avoiding geometric progressions., Comment: 16 pages

Lehmer's totient problem asks if there exist composite integers n satisfying the condition phi(n)|(n-1), (where phi is the Euler-phi function) while Carmichael numbers satisfy the weaker condition lambda(n)|(n-1) (where lambda is the Carmichael universal exponent function). We weaken the condition further, looking at those composite n where each prime divisor of phi(n) also divides n-1. (So rad(phi(n))|(n-1).) While these numbers appear to be far more numerous than the Carmichael numbers, we show that their distribution has the same rough upper bound as that of the Carmichael numbers, a bound which is heuristically tight., Comment: 10 pages