Counting primitive subsets and other statistics of the divisor graph of \1,2,,n\

DOI10.1016/J.EJC.2020.103237MaRDI QIDQ2225441zbMATH OpenOpenAlexFDO

Authors Nathan McNew

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.04923

zbMATH Keywords

asymptoticscombinatorial number theorydivisor graphpath coversprimitive subsetsprogression-free subsets

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Asymptotic results on arithmetic functions (11N37)

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

Review text

The author proves a formula that allows one to systematically study the rate of growth of certain counting functions in number theory. More precisely, consider the divisor graph, whose vertices are the integers \(\{a,\dots, m\}\) and are linked iff one divides the other. The functions of \((a,m)\) on which the main result applies are those that depend only on the graph-isomorphy class of the connected component of \(a\) in this graph. Many applications are discussed: an alternative proof of the asymptotic number of primitive subsets of integers \(\leq n\) is given, with improved bounds on the exponential rate, and improved second terms; the number of primitive subsets of maximal size is shown to behave similarly. In both cases the exponential rate can be approximated with arbitrary precision. The method is then applied to maximal primitive subsets, and for the median size of primitive subsets -- with the question of proving linear asymptotics in the last case left open. Finally, the number of paths in a minimal path cover, and the size of largest subsets avoiding 3-term geometric progressions, as well as the number of progression-free subsets, are also considered.

Recommendations

• Primitive sets with large counting functions
• A Cameron and Erdős conjecture on counting primitive sets
• On the counting function of primitive sets of integers.
• Study of the divisor graph. I
• Sur un problème de crible et ses applications. II. Corrigendum et étude du graphe divisoriel

Cites work

• A Cameron and Erdős conjecture on counting primitive sets
• Hamiltonian coverings of some graphs
• scientific article; zbMATH DE number 3169559 (Why is no real title available?)
• scientific article; zbMATH DE number 3869367 (Why is no real title available?)
• scientific article; zbMATH DE number 4137896 (Why is no real title available?)
• scientific article; zbMATH DE number 473229 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• Integers with a large friable component
• Multiplicative structures in additively large sets
• On path partitions of the divisor graph
• On path partitions of the divisor graph
• On sequences without geometric progressions
• On sets of integers which contain no three terms in geometric progression
• On sharp transitions in making squares
• Opera de cribro
• Sets of integers containing no n terms in geometric progression
• Study of the divisor graph. III
• Sur le graphe divisoriel

Cited in

(8)

• Study of the divisor graph. I
• The number of multiplicative Sidon sets of integers
• Sur un problème de crible et ses applications. II. Corrigendum et étude du graphe divisoriel
• Coprime permutations
• Some results about maximal primitive sets
• Permutations and the divisor graph of [1,n]
• Permutations with arithmetic constraints
• On the homology of several number-theoretic set families

Describes a project that uses

Uses Software

• OEIS
• SageMath

This page was built for publication: Counting primitive subsets and other statistics of the divisor graph of \(\{1,2,\dots,n\}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225441)