# Modular Egyptian fractions

For a prime p, define f(p) to be the minimum i such that all residues mod p can be expressed as sums of subsets of the values {1/1, 1/2, 1/3, ...1/i} mod p. We need only consider residues other than 0 and 1, since 0 is always the sum of the empty subset and 1 = 1/1. E.g.,

f(2) = 1, because 1 = 1/1.

f(3) = 2, because 2 = 1/2 mod 3.

f(5) = 3, because 2 = 1/3, 3 = 1/2, and 4 = 1/1 + 1/2 mod 5.

f(7) = 3, because 2 = 1/2 + 1/3, 3 = 1/1 + 1/2 + 1/3, 4 = 1/2, 5 = 1/3, and 6 = 1/1 + 1/3 mod 7.

f(11) = 4, because 2 = 1/2 + 1/3 + 1/4, 3 = 1/4, 4 = 1/3, 5 = 1/1 + 1/3, 6 = 1/2, 7 = 1/1 + 1/2, 8 = 1/1 + 1/3 + 1/4, 9 = 1/2 + 1/4, and 10 = 1/2 + 1/3 mod 11.

f(13) = 5. 2 = 1/2 + 1/5 (mod 13) and 12 = 1/1 + 1/2 + 1/3 + 1/5 (mod 13); all other residues can be expressed as sums of subsets of {1/1, 1/2, 1/3, 1/4}.

How quickly does f(p) grow with p? It must be at least log

The relevance of this is for bounding the maximum denominator of an Egyptian fraction as a function of its denominator. For each p, some fraction x/p requires a maximum denominator of at least f(p)p in any Egyptian fraction expansion, as can be seen by considering only the terms in the expansion in which the denominator is a multiple of p. The simple lower bound for f(p) above thus leads to a lower bound of Ω(y log y) on the maximum denominator in an expansion of x/y, for infinitely many pairs x, y. On the other hand, it seems plausible (although not completely obvious due to issues with repeated fractions and overlarge expansions) that something like the prime-multiples method of my Egyptian fraction code can expand any fraction x/y using max denominator f(p)y, where p is the prime factor of y with the largest value of f(p). This approach might have some hope of improving the Tenenbaum-Yokota O(y log^2 y / log log y) upper bound on the max denominator.

f(2) = 1, because 1 = 1/1.

f(3) = 2, because 2 = 1/2 mod 3.

f(5) = 3, because 2 = 1/3, 3 = 1/2, and 4 = 1/1 + 1/2 mod 5.

f(7) = 3, because 2 = 1/2 + 1/3, 3 = 1/1 + 1/2 + 1/3, 4 = 1/2, 5 = 1/3, and 6 = 1/1 + 1/3 mod 7.

f(11) = 4, because 2 = 1/2 + 1/3 + 1/4, 3 = 1/4, 4 = 1/3, 5 = 1/1 + 1/3, 6 = 1/2, 7 = 1/1 + 1/2, 8 = 1/1 + 1/3 + 1/4, 9 = 1/2 + 1/4, and 10 = 1/2 + 1/3 mod 11.

f(13) = 5. 2 = 1/2 + 1/5 (mod 13) and 12 = 1/1 + 1/2 + 1/3 + 1/5 (mod 13); all other residues can be expressed as sums of subsets of {1/1, 1/2, 1/3, 1/4}.

How quickly does f(p) grow with p? It must be at least log

_{2}p else there would not be enough different subsets to cover all the residues. It seems plausible to me (e.g. using an argument in which we replace each unit fraction by a random variable) that f(p) = Θ(log p).The relevance of this is for bounding the maximum denominator of an Egyptian fraction as a function of its denominator. For each p, some fraction x/p requires a maximum denominator of at least f(p)p in any Egyptian fraction expansion, as can be seen by considering only the terms in the expansion in which the denominator is a multiple of p. The simple lower bound for f(p) above thus leads to a lower bound of Ω(y log y) on the maximum denominator in an expansion of x/y, for infinitely many pairs x, y. On the other hand, it seems plausible (although not completely obvious due to issues with repeated fractions and overlarge expansions) that something like the prime-multiples method of my Egyptian fraction code can expand any fraction x/y using max denominator f(p)y, where p is the prime factor of y with the largest value of f(p). This approach might have some hope of improving the Tenenbaum-Yokota O(y log^2 y / log log y) upper bound on the max denominator.