INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A01

AFFINE INVARIANTS, RELATIVELY PRIME SETS, AND A PHI FUNCTION FOR SUBSETS OF {1, 2, …, N}

Melvyn B. Nathanson^{1}

Lehman College (CUNY), Bronx, New York 10468

                      melvyn.nathanson@lehman.cuny.edu

Received: 8/15/06, Accepted: 12/29/06, Published: 1/3/07

Abstract

A nonempty subset A of {1, 2, …, n} is relatively prime if gcd(A) = 1. Let f(n) and f_{k}(n) denote, respectively, the number of relatively prime subsets and the number of relatively prime subsets of cardinality k of {1, 2, …, n}. Let Φ(n) and Φ_{k}(n) denote, respectively, the number of nonempty subsets and the number of subsets of cardinality k of {1, 2, …, n} such that gcd(A) is relatively prime to n. Exact formulas and asymptotic estimates are obtained for these functions.

Subject class: Primary 11A25, 11B05, 11B13, 11B75.

Keywords: Relatively prime sets, Euler phi function, combinatorial

1. Affine Invariants

Let A be a set of integers, and let x and y be rational numbers. We define the dilation x ∗ A = {xa : a ∈ A} and the translation A + y = {a + y : a ∈ A}. Sets of integers A and B are affinely equivalent if there exist rational numbers x ≠ 0 and y such that B = x∗A+y. For example, the sets A = {2, 8, 11, 20} and B = {−4, 10, 17, 38} are affinely equivalent, since B = (7/3) ∗ A − 26/3, and A and B are both affinely equivalent to the sets C = {0, 2, 3, 6} and D = {0, 3, 4, 6}. Every set with one element is affinely equivalent to {0}. Every finite set A of integers with more than one element is affinely equivalent to unique sets C and D of nonnegative integers such that min(C) = min(D) = 0, gcd(C) = gcd(D) = 1, and D = (−1) ∗ C + max(C).

A function f(A) whose domain is the set F(Z) of nonempty finite sets of integers is called an affine invariant of F(Z) if f(A) = f(B) for all affinely equivalent sets A and B.

1This work was supported in part by grants from the NSA Mathematical Sciences Program and the PSC-CUNY Research Award Program.

For example, if A + A = {a + a′ : a, a′ ∈ A} is the sumset of a finite set A of integers, and if A − A = {a − a′ : a, a′ ∈ A} is the difference set of the finite set A, then s(A) = card(A + A) and d(A) = card(A − A) are affine invariants. More generally, let u_{0}, u_{1}, …, u_{n} be integers and F (x_{1}, …, x_{n}) = u_{1}x_{1} + ⋯ + u_{n}x_{n} + u_{0}. Define F (A) = {u_{1}a_{1} + ⋯ + u_{n}a_{n} + u_{0} : a_{1}, …, a_{n} ∈ A for i = 1, …, n}. Then f(A) = card(F (A)) is an affine invariant.

Let f(A) be a function with domain F(Z). A frequent problem in combinatorial number theory is to determine the distribution of values of the function f(A) for sets A in the interval of integers {0, 1, …, n}. For example, if A ⊆ {0, 1, 2, …, n}, then 1 ≤ card(A+A) ≤ 2n+1. For ℓ = 1, …, 2n + 1, we can ask for the number of nonempty sets A ⊆ {0, 1, 2, …, n} such that card(A + A) = ℓ. Similarly, if ∅ ≠ A ⊆ {0, 1, 2, …, n} and card(A) = k, then 2k − 1 ≤ card(A + A) ≤ k(k + 1)/2, and, for ℓ = 2k − 1, …, k(k + 1)/2, we can ask for the number of such sets A with card(A + A) = ℓ. In both cases, there is a redundancy in considering sets that are affinely equivalent, and we might want to count only sets that are pairwise affinely inequivalent.

2. Relatively Prime Sets

A nonempty subset A of {1, 2, …, n} will be called relatively prime if the elements of A are relatively prime, that is, if gcd(A) = 1. Let f(n) denote the number of relatively prime subsets of {1, 2, …, n}. The first 10 values of f(n) are 1, 2, 5, 11, 26, 53, 116, 236, 488, and 983. (This is sequence A085945 in Sloane’s On-Line Encyclopedia of Integer Sequences.) Let f_{k}(n) denote the number of relatively prime subsets of {1, 2, …, n} of cardinality k. We present exact formulas and asymptotic estimates for f(n) and f_{k}(n). These estimates imply that almost all finite sets of integers are relatively prime.

No set of even integers is relatively prime. Since there are 2^{[n/2]} − 1 nonempty subsets of {2, 4, 6, …, 2[n/2]} and 2^{n} − 1 nonempty subsets of {1, 2, …, n}, we have the upper bound

f(n) ≤ 2^{n} − 2^{[n/2]}.  (1)

Similarly,

f_{k}(n) ≤ \binom{n}{k} − \binom{[n/2]}{k}.  (2)

If 1 ∈ A, then A is relatively prime. Since there are 2^{n−1} sets A ⊆ {1, 2, …, n} with 1 ∈ A, we have

f(n) ≥ 2^{n−1}.

Let n ≥ 3. If 1 ∉ A but 2 ∈ A and 3 ∈ A, then A is relatively prime and so

f(n) ≥ 2^{n−1} + 2^{n−3}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A01 3

Let n ≥ 5. If 1 ∉ A and 3 ∉ A, but 2 ∈ A and 5 ∈ A, then A is relatively prime. If 1 ∉ A and 2 ∉ A, but 3 ∈ A and 5 ∈ A, then A is relatively prime. Therefore,

f(n) ≥ 2^{n−1} + 2^{n−3} + 2 · 2^{n−4} = 2^{n−1} + 2^{n−2}.

Similarly,

f_{k}(n) ≥ \binom{n − 1}{k − 1} + \binom{n − 3}{k − 2} + 2\binom{n − 4}{k − 2}.

3. Exact Formulas and Asymptotic Estimates Let [x] denote the greatest integer less than or equal to x. If x ≥ 1 and n = [x], then

[\frac{x}{d}] = [\frac{[x]}{d}] = [\frac{n}{d}]

for all positive integers d.

Let F (x) be a function defined for x ≥ 1, and define the function

G(x) = ∑_{1≤d≤x} F (\frac{x}{d}) .

In the proof of Theorem 1 we use the following version of the Möbius inversion formula (Nathanson [1, Exercise 5 on p. 222]):

F (x) = ∑_{1≤d≤x} μ(d)G (\frac{x}{d}) .

Theorem 1 For all positive integers n,

∑_{d=1}^{n} f ([\frac{n}{d}]) = 2^{n} − 1  (3)

and

f(n) = ∑_{d=1}^{n} μ(d) (2^{[n/d]} − 1) .  (4)

For all positive integers n and k,

∑_{d=1}^{n} f_{k} ([\frac{n}{d}]) = \binom{n}{k}  (5)

and

f_{k}(n) = ∑_{d=1}^{n} μ(d)\binom{[n/d]}{k}.  (6)

Proof. Let A be a nonempty subset of {1, 2, …, n}. If gcd(A) = d, then A′ = (1/d) ∗ A = {a/d : a ∈ A} is a relatively prime subset of {1, 2, …, [n/d]}. Conversely, if A′ is a relatively prime subset of {1, 2, …, [n/d]}, then A = d ∗ A′ = {da′ : a′ ∈ A′} is a nonempty subset of {1, 2, …, n} with gcd(A) = d. It follows that there are exactly f([n/d]) subsets A of {1, 2, …, n} with gcd(A) = d, and so

∑_{d=1}^{n} f ([\frac{n}{d}]) = 2^{n} − 1.

We apply Möbius inversion to the function F (x) = f([x]). For all x ≥ 1 we define

G(x) = ∑_{1≤d≤x} F (\frac{x}{d}) = ∑_{1≤d≤x} f ([\frac{x}{d}]) = ∑_{d=1}^{[x]} f ([\frac{[x]}{d}]) = 2^{[x]} − 1

and so

f([x]) = F (x) = ∑_{1≤d≤x} μ(d)G (\frac{x}{d}) = ∑_{d=1}^{[x]} μ(d) (2^{[x/d]} − 1) .

For n ≥ 1 we have

f(n) = ∑_{d=1}^{n} μ(d) (2^{[n/d]} − 1) .

The proofs of (5) and (6) are similar. □

Theorem 2 For all positive integers n and k,

2^{n} − 2^{[n/2]} − n2^{[n/3]} ≤ f(n) ≤ 2^{n} − 2^{[n/2]}

and

\binom{n}{k} − \binom{[n/2]}{k} − n\binom{[n/3]}{k} ≤ f_{k}(n) ≤ \binom{n}{k} − \binom{[n/2]}{k}.

Proof. For n ≥ 2 we have

2^{n} = f(n) + f([n/2]) + ∑_{d=3}^{n} f ([\frac{n}{d}]) + 1 ≤ f(n) + 2^{[n/2]} + n2^{[n/3]}.

Combining this with (1), we obtain

2^{n} − 2^{[n/2]} − n2^{[n/3]} ≤ f(n) ≤ 2^{n} − 2^{[n/2]}.

This also holds for n = 1.

The inequality for f_{k}(n) follows similarly from (2) and (5). □

Theorem 2 implies that f(n) ∼ 2^{n} as n → ∞, and so almost all finite sets of integers are relatively prime.

4. A phi Function for Sets

The Euler phi function φ(n) counts the number of positive integers a ≤ n such that a is relatively prime to n. We define the function Φ(n) to be the number of nonempty subsets A of {1, 2, …, n} such that gcd(A) is relatively prime to n. For example, for distinct primes p and q we have

Φ(p) = 2^{p} − 2
Φ(p^{2}) = 2^{p^{2}} − 2^{p}

and

Φ(pq) = 2^{pq} − 2^{q} − 2^{p} + 2.

Define the function Φ_{k}(n) to be the number of subsets A of {1, 2, …, n} such that card(A) = k and gcd(A) is relatively prime to n. Note that Φ_{1}(n) = φ(n) for all n ≥ 1.

Theorem 3 For all positive integers n,

∑_{d|n} Φ (d) = 2^{n} − 1.  (7)

Moreover, Φ(1) = 1 and, for n ≥ 2,

Φ(n) = ∑_{d|n} μ (d) 2^{n/d}  (8)

where μ(n) is the Möbius function. Similarly, for all positive integers n and k,

∑_{d|n} Φ_{k}(d) = \binom{n}{k}  (9)

and

Φ_{k}(n) = ∑_{d|n} μ (d) \binom{n/d}{k}  (10)

Proof. For every divisor d of n, we define the function Ψ(n, d) to be the number of nonempty subsets A of {1, 2, …, n} such that the greatest common divisor of gcd(A) and n is d. Thus,

Ψ(n, d) = card ({A ⊆ {1, 2, …, n} : A ≠ ∅ and gcd(A ∪ {n}) = d}) .

Then

Ψ(n, d) = Φ (\frac{n}{d})

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A01 6

and

2^{n} − 1 = ∑_{d|n} Ψ(n, d) = ∑_{d|n} Φ (\frac{n}{d}) = ∑_{d|n} Φ(d).

We have Φ(1) = 1. For n ≥ 2 we apply the usual Möbius inversion and obtain

Φ(n) = ∑_{d|n} μ (d) (2^{n/d} − 1)

= ∑_{d|n} μ (d) 2^{n/d} − ∑_{d|n} μ (d)

= ∑_{d|n} μ (d) 2^{n/d}

since ∑_{d|n} μ(n/d) = 0 for n ≥ 2.

The proofs of (9) and (10) are similar. □ Theorem 4 If n is odd, then

Φ(n) = 2^{n} + O (n2^{n/3})

and

Φ_{k}(n) = \binom{n}{k} + O (n\binom{[n/3]}{k}) .

If n is even, then

Φ(n) = 2^{n} − 2^{n/2} + O (n2^{n/3})

and

Φ_{k}(n) = \binom{n}{k} − \binom{n/2}{k} + O (n\binom{[n/3]}{k}) .

Proof. We have

Φ(n) = ∑_{\begin{matrix}d=1 \\ gcd(d,n)=1 \end{matrix}}^{n} card (\{A ⊆ \{1, 2, …, n\} : A ≠ ∅ and gcd(A) = d\})

= ∑_{\begin{matrix}d=1 \\ gcd(d,n)=1 \end{matrix}}^{n} f([n/d]).

Applying Theorem 2, we see that if n is odd, then

Φ(n) = f(n) + f([n/2]) + ∑_{\begin{matrix}d=3 \\ gcd(d,n)=1 \end{matrix}}^{n} f([n/d])

= (2^{n} − 2^{[n/2]} + O (n2^{n/3})) + (2^{[n/2]} + O (2^{n/4})) + O (n2^{n/3})
= 2^{n} + O (n2^{n/3}) .

If n is even, then

Φ(n) = f(n) + ∑_{\begin{matrix}d=3 \\ gcd(d,n)=1 \end{matrix}}^{n} f([n/d])

= (2^{n} − 2^{n/2} + O (n2^{n/3})) + O (n2^{n/3})
= 2^{n} − 2^{n/2} + O (n2^{n/3}) .

These estimates for Φ(n) also follow from identity (8). The estimates for Φ_{k}(n) follow from identity (10). This completes the proof. □

Acknowledgements. I thank Greg Martin for the observation that (4) and (6) follow from (3) and (5) by Möbius inversion, and Kevin O’Bryant for helpful discussions.

References

[1] M. B. Nathanson, Elementary Methods in Number Theory, Graduate Texts in Mathematics, vol. 195, Springer-Verlag, New York, 2000.