Elementary details used in the proofs
Cyclotomic prime-power fact.
Let 𝑏 ≥2, 𝑛 ≥2, ℓ ∣Φ𝑛(𝑏) be prime and 𝑒 =𝑣ℓ(𝑏𝑛 −1). Then ordℓ𝑒(𝑏) =𝑛. We
include the 2-adic case. For odd
ℓ, put 𝑑 =ordℓ(𝑏) and 𝑠 =𝑣ℓ(𝑏𝑑 −1). The elementary lifting
identity 𝑣ℓ(𝑏𝑑𝑡 −1) =𝑠 +𝑣ℓ(𝑡) follows by
factoring a geometric sum when ℓ ∤𝑡 and by a binomial expansion for a factor ℓ. In the factorisation 𝑏𝑛 −1 =∏𝑟∣𝑛Φ𝑟(𝑏),
subtracting these valuations over proper divisors gives
𝑣ℓ(Φ𝑛(𝑏))={𝑠𝑛=𝑑,1𝑛=𝑑ℓ𝑗, 𝑗≥1,0otherwise.
If 𝑛 =𝑑, no smaller positive exponent gives
𝑏𝑚 ≡1(modℓ). If 𝑛 =𝑑ℓ𝑗, the full valuation is 𝑒 =𝑠 +𝑗; the same lifting identity shows
that the least exponent giving valuation 𝑒 is 𝑑ℓ𝑗 =𝑛. For ℓ =2, 𝑏 is odd. Factoring 𝑏2𝑡 −1 gives
𝑣2(𝑏2𝑗−1)=𝑣2(𝑏−1)+𝑣2(𝑏+1)+𝑗−1(𝑗≥1).
The only possible indices 𝑛 ≥2 are
𝑛 =2𝑗: 𝑣2(Φ2(𝑏)) =𝑣2(𝑏 +1) and 𝑣2(Φ2𝑗(𝑏)) =1 for 𝑗 ≥2; all other indices have valuation
zero. The displayed identity again makes 2𝑗 the least exponent with the full
valuation. This proves the fact. Finally Φ𝑛(𝑏) >1: each primitive 𝑛th root 𝜁 satisfies |𝑏 −𝜁| >1, and their product is
Φ𝑛(𝑏).
Exact scalar cover cost.
For 𝑡 ≥1, put 𝑧 =log2𝑡. The substitution 𝑦 =2𝛼 reduces the infimum defining
Ψ(𝑡) to 𝑦𝑧/(𝑦 −1) on 1 <𝑦 ≤2. Its derivative has the sign
of (𝑧 −1)𝑦 −𝑧. Hence
Ψ(𝑡)={𝑡,1≤𝑡≤4,𝑧𝑧/(𝑧−1)𝑧−1,𝑡>4.
The minimum is at 𝛼 =1 for 𝑡 ≤4 and in the interior for 𝑡 >4; the quotient diverges as 𝛼 ↓0. This scalar identity
does not supply a converse to the positive-cover criterion.
The cost for a finite set of divisors
For the following finite divisor sets, the lower bound is
asymptotically attained. Here 𝐾∗(𝐹) is the infimum of the cost 𝐾 from Section 5 over finite or
countable covers of 𝐹, their
majorants and exponents, and positive weights of total one. A one-set
cover therefore has weight 1,
without the dyadic index factor in (V). For 𝐹(𝑞,𝑃) ={𝑞𝑑 :𝑑 ∣∏𝑝∈𝑃𝑝}, where
𝑞 ≥2 and no 𝑝 ∈𝑃 divides 𝑞, put 𝑆 =∑𝑝∈𝑃1/𝑝. If 𝑆 ≥1, then
𝑒(𝑆−1)𝑞≤𝐾∗(𝐹(𝑞,𝑃))≤𝑒𝑆𝑞.(13)
For the lower bound, we condition on 𝑞 ∣𝑛 and write 𝑓𝐹(𝑛) =2𝑍. The Chinese remainder theorem
gives 𝔼𝑍 =𝑆. For 𝑧 ≥0 and 𝑣 =𝛼log2 >0,
2𝛼𝑧2𝛼−1≥𝑒(𝑧−1)𝑣𝑣≥𝑒(𝑧−1)(𝑧>1);
for 0 ≤𝑧 ≤1 the claimed lower bound is
nonpositive. Thus Ψ(2𝑧) ≥𝑒(𝑧 −1); averaging and multiplying by the density 1/𝑞 gives the lower bound. For the upper
bound, use the one-set cover with 𝑧 =1/𝑆 and 𝛼 =log2(1 +𝑧); its exact positive
expansion has cost
1𝑞𝑧∏𝑝∈𝑃(1+𝑧/𝑝)≤𝑒𝑆𝑞.
In particular, 1 −1/𝑆 ≤𝑞𝐾∗(𝐹(𝑞,𝑃))/(𝑒𝑆) ≤1. Thus
𝐾∗(𝐹(𝑞,𝑃)) ∼𝑒𝑆/𝑞 as 𝑆 →∞, uniformly over the permitted
choices of 𝑞 and 𝑃.