6
$\begingroup$

I am working on a problem in which it is important to study the maximal coprime-free subsets of $[n] = \{1,2,\ldots,n\}$. (A set $S\subseteq [n]$ is coprime-free if for all $i,j\in S$ with $i\ne j$, $\gcd(i,j)\ne 1$. I'm counting the maximal ones, namely coprime-free $S$ such that for all $x\in [n]\setminus S$, $S\cup\{x\}$ is not coprime-free.) For a while I was working under the impression that, other than the exceptional case $\{1\}$, these sets were of the form $p{\bf N} \cap [n]$ for all primes $p\in [n]$. But this turns out not to be the case. For example, when $n=15$, there is the maximal subset $\{6,10, 12,15\}$, which is not of the form $p{\bf N}\cap [15]$ for any of the six primes less than $15$.

Would anyone happen to know if these maximal coprime-free subsets admit any kind of simple description? Thank you in advance!

$\endgroup$
4
  • $\begingroup$ Let $k \ge 1$. If $p_1,\ldots,p_{2k-1}$ are distinct fixed prime numbers in $[n]$, then the set of all integers which are divisible by at least $k$ prime numbers among $p_1,\ldots,p_{2k-1}$ is coprime-free and looks maximal. Your example corresponds to the case where $k=2$ and $p_1,p_2,p_3$ are $2,3,5$. $\endgroup$ Commented Jan 30, 2023 at 8:54
  • 2
    $\begingroup$ @ChristopheLeuridan Note also the existence of maximal coprime-free sets that don't follow this pattern; say {14, 26, 28, 42, 52, 56, 70, 78, 84, 91, 98} = {2·7, 2·13, 2²·7, 2·3·7, 2²·13, 2³·7, 2·5·7, 2·3·13, 2²·3·7, 7·13, 2·7²} in [100]. $\endgroup$ Commented Jan 30, 2023 at 9:13
  • $\begingroup$ Playing on my computer, it seems there always exist primes $p,q$ such that $S\subseteq p\mathbf N\cup q\mathbf N$; and often there are integers $j,k$ such that most multiples of $p$ and $q$ are actually multiples of $jp$ and $kq$ respectively. Interesting examples: If we write $m\cdot S=\{ms:s\in S\}$, then 7·{3, 6, 9, 12} ∪ 13·{3, 6} ∪ {7·13} is maximal in [100]; and so are 5·{3, 6, 9, 12, 15, 18} ∪ 11·{3, 6, 9} ∪ {5·11} and {5·7, 5·13, 2·5·7, 7·13}. Also, 29·{2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 15, 16} ∪ {2·3·5·13} is maximal in [500]; and so is 29·{3, 6, 9, 11, 12, 13, 15} ∪ {3·11·13}. $\endgroup$ Commented Jan 30, 2023 at 15:27
  • $\begingroup$ Thanks for your observations/computations! I think looking at the variation in @hoboonsuan's examples, I'm a bit less hopeful now that there are easily-described necessary and sufficient conditions, but one can always hope! I'll continue investigating on my end and add an update if I find anything of note. $\endgroup$ Commented Jan 30, 2023 at 16:46

0

You must log in to answer this question.

Browse other questions tagged .