Znám's problem

From Wikipedia, the free encyclopedia

Graphical demonstration that 1 = 1/2 + 1/3 + 1/11 + 1/23 + 1/31 + 1/(2×3×11×23×31). Each row of k squares of side length 1/k has total area 1/k, and all the squares together exactly cover a larger square with area 1. The bottom row of 47058 squares with side length 1/47058 is too small to see in the figure and is not shown.

In number theory, Znám's problem asks which sets of integers have the property that each integer in the set is a proper divisor of the product of the other integers in the set, plus 1. That is, given k, what sets of integers

$\{n_1, \ldots, n_k\}$

are there, such that, for each i, n_i divides but is not equal to

$\prod_{j \ne i}^n n_j + 1?$

A closely related problem concerns sets of integers in which each integer in the set is a divisor, but not necessarily a proper divisor, of one plus the product of the other integers in the set. This problem does not seem to have been named in the literature, but for ease of description we refer to it as the improper Znám problem. Any solution to Znám's problem is also a solution to the improper Znám problem, but not necessarily vice versa.

Znám's problem is named after Slovak mathematician Štefan Znám, who suggested it in 1972. Barbeau (1971) had posed the improper Znám problem for k = 3, and Mordell (1973) independently of Znám found all solutions to the improper problem for k ≤ 5. Skula (1975) showed that Znám's problem is unsolvable for k < 5, and credited J. Janák with finding the solution {2, 3, 11, 23, 31} for k = 5.

The improper Znám problem is easily solved for any k: the first k terms of Sylvester's sequence provide a solution. Sun (1983) showed that there is at least one solution to Znám's problem for each k ≥ 5. Sun's solution is based on a recurrence similar to that for Sylvester's sequence, but with a different set of initial values.

It is unknown whether there are any solutions to Znám's problem using only odd numbers. With one exception, all known solutions start with 2. If all numbers in a solution to Znám's problem or the improper Znám problem are prime, their product is a primary pseudoperfect number (Butske et al. 2000); it is unknown whether infinitely many solutions of this type exist.

1 Examples
2 Connection to Egyptian fractions
3 Number of solutions
4 References
5 External links

[edit] Examples

One solution to k = 5 is {2, 3, 7, 47, 395}. A few calculations will show that

3 × 7 × 47 × 395	+ 1 =	389866,	which is divisible by but unequal to 2,
2 × 7 × 47 × 395	+ 1 =	259911,	which is divisible by but unequal to 3,
2 × 3 × 47 × 395	+ 1 =	111391,	which is divisible by but unequal to 7,
2 × 3 × 7 × 395	+ 1 =	16591,	which is divisible by but unequal to 47, and
2 × 3 × 7 × 47	+ 1 =	1975,	which is divisible by but unequal to 395.

An interesting "near miss" for k = 4 is the set {2, 3, 7, 43}, formed by taking the first four terms of Sylvester's sequence. It has the property that each integer in the set divides the product of the other integers in the set, plus 1, but the last member of this set is equal to the product of the first three members plus one, rather than being a proper divisor. Thus, it is a solution to the improper Znám problem, but not a solution to Znám's problem as it is usually defined.

[edit] Connection to Egyptian fractions

Any solution to the improper Znám problem is equivalent (via division by the product of the x_i's) to a solution to the equation

$\sum\frac1{x_i} + \prod\frac1{x_i}=y,$

where y as well as each x_i must be an integer, and conversely any such solution corresponds to a solution to the improper Znám problem. However, all known solutions have y = 1, so they satisfy the equation

$\sum\frac1{x_i} + \prod\frac1{x_i}=1.$

That is, they lead to an Egyptian fraction representation of the number one as a sum of unit fractions. Several of the cited papers on Znám's problem study also the solutions to this equation. Brenton and Hill (1988) describe an application of the equation in topology, to the classification of singularities on surfaces, and Domaratzki et al. (2005) describe an application to the theory of nondeterministic finite automata.

[edit] Number of solutions

As Janák and Skula (1978) showed, the number of solutions for any k is finite, so it makes sense to count the total number of solutions for each k.

Brenton and Vasiliu calculated that the number of solutions for small values of k, starting with k = 5, forms the sequence

2, 5, 15, 93 (sequence A075441 in OEIS).

Presently, a few solutions are known for k = 9 and k = 10, but it is unclear how many solutions remain undiscovered for those values of k. However, there are infinitely many solutions if k is not fixed: Cao and Jing (1998) showed that there are at least 39 solutions for each k ≥ 12, improving earlier results proving the existence of fewer solutions (Cao et al 1987; Sun and Cao 1988). Sun and Cao (1988) conjecture that the number of solutions for each value of k grows monotonically with k.

[edit] References

Barbeau, G. E. J. (1971). "Problem 179". Canad. Math. Bull. 14 (1): 129.

Brenton, Lawrence and Hill, Richard (1988). "On the Diophantine equation 1=Σ1/n_i + 1/Πn_i and a class of homologically trivial complex surface singularities". Pacific Journal of Mathematics 133 (1): 41–67. MR 0936356.

Brenton, Lawrence and Vasiliu, Ana (2002). "Znám's problem". Mathematics Magazine 75: 3–11.

Butske, William, Jaje, Lynda M., and Mayernik, Daniel R. (2000). "On the equation $\scriptstyle\sum_{p|N}\frac{1}{p}+\frac{1}{N}=1$ , pseudoperfect numbers, and perfectly weighted graphs". Mathematics of Computation 69: 407–420. MR 1648363.

Cao, Zhen Fu; Jing, Cheng Ming (1998). "On the number of solutions of Znám's problem". J. Harbin Inst. Tech. 30 (1): 46–49. MR 1651784.

Cao, Zhen Fu; Liu, Rui; Zhang, Liang Rui (1987). "On the equation $\scriptstyle\sum^s_{j=1}(1/x_j)+(1/(x_1\cdots x_s))=1$ and Znám's problem". Journal of Number Theory 27 (2): 206–211. DOI:10.1016/0022-314X(87)90062-X. MR 0909837.

Domaratzki, Michael; Ellul, Keith; Shallit, Jeffrey; Wang, Ming-Wei (2005). "Non-uniqueness and radius of cyclic unary NFAs". International Journal of Foundations of Computer Science 16 (5): 883–896. DOI:10.1142/S0129054105003352. MR 2174328.

Janák, Jaroslav; Skula, Ladislav (1978). "On the integers $\scriptstyle x_{i}$ for which $\scriptstyle x_{i}|x_{1}\cdots x_{i-1}x_{i+1}\cdots x_{n}+1$ ". Math. Slovaca 28 (3): 305–310. MR 0534998.

Mordell, L. J. (1973). "Systems of congruences.". Canad. Math. Bull. 16: 457–462. MR 0332650.

Skula, Ladislav (1975). "On a problem of Znám" (Russian, Slovak summary). Acta Fac. Rerum Natur. Univ. Comenian. Math. 32: 87–90. MR 0539862.

Sun, Qi (1983). "On a problem of Š. Znám". Sichuan Daxue Xuebao (4): 9–12. MR 0750288.

Sun, Qi; Cao, Zhen Fu (1988). "On the equation $\scriptstyle\sum^s_{j=1}1/x_j+1/x_1\cdots x_s=n$ and the number of solutions of Znám's problem". Northeastern Mathematics Journal 4 (1): 43–48. MR 0970644.