A counterexample to a subadditivity conjecture of Cohen for Sophie Germain cyclic numbers

Abstract

An integer $n\ge 1$ is cyclic if $\gcd (n,\phi (n))=1$ (equivalently, if every group of order $n$ is cyclic), and Sophie Germain cyclic if both $n$ and $2n+1$ are cyclic. Let $C_{\sigma }(N)$ count the Sophie Germain cyclic integers in $[1,N]$. Cohen conjectured that $C_{\sigma }$ is subadditive, $C_{\sigma }(m+n)\le C_{\sigma }(m)+C_{\sigma }(n)$ for all $1\le m\le n$ (his Conjecture 66), having checked $m,n\le 10^6$ without finding a counterexample. We give one: at $m=31$, $n=3928$, $C_{\sigma }(3959)=697>696=C_{\sigma }(31)+C_{\sigma }(3928)$. The argument is short, and is verified by the Lean 4 kernel.

3 pages. Ancillary file: Lean 4 formalization (anc/cohen66.lean); the refutation is Lean kernel-checked, depending only on propext, Classical.choice, and Quot.sound