Primitive Sets with Small Gaps

by radimentary

A primitive set is a set $S$ of positive integers such that no pair of distinct elements $a,b\in S$ satisfies $a | b$ .

A square-primitive set is a set of positive integers $S$ such that no pair of distinct elements $a, b \in S$ has ratio $a/b$ equal to an square integer.

In the following writeup, I show how to construct square-primitive sets with very short gaps $O_{\epsilon} ((\log N)^2 (\log \log N)^{\epsilon})$ . This relies on dividing the poset $\mathbb{N}$ ordered by divisibility into antichains $A_m$ consisting of all numbers in $\mathbb{N}$ with exactly $m$ (not necessarily distinct) prime factors, and then picking one randomly.

Square Primitive Sets With Small Gaps

I’m interested in the much harder problem of constructing primitive sets with similarly small gaps. To do this using the same method requires a way to randomly generate infinite antichains of $\mathbb{N}$ . Here is a naive way to do this: take every positive integer $n$ and attach to it a weight $f(n)\in [0,1]$ . Sort the naturals by size, and at each $n$ , flip an $f(n)$ -weighted coin in our antichain $A$ if no divisor of $n$ has been included yet, and add $n$ to $A$ if it comes up heads. In general, we should expect $A$ to always be infinite if $f(1)=0$ , and hopefully have small gaps.