Znám's problem

In number theory, Znám's problem asks which sets of "k" 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. Znám's problem is named after the Slovak mathematician Štefan Znám, who suggested it in 1972, although other mathematicians had considered similar problems around the same time. One closely related problem drops the assumption of properness of the divisor, and will be called the improper Znám problem hereafter.

One solution to the improper Znám problem is easily provided for any "k": the first "k" terms of Sylvester's sequence have the required property. harvtxt|Sun|1983 showed that there is at least one solution to the (proper) Znám 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.

The Znám problem is closely related to Egyptian fractions. It is known that there are only finitely many solutions for any fixed "k". It is unknown whether there are any solutions to Znám's problem using only odd numbers, and there remain several other open questions.

The problem

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:$Bigl(prod\_\{j\; e\; i\}^n\; n\_jBigr)\; +\; 1quad\; ?$

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, and will be referred to 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.

History

Znám's problem is named after the Slovak mathematician Štefan Znám, who suggested it in 1972. harvtxt|Barbeau|1971 had posed the improper Znám problem for "k" = 3, and harvtxt|Mordell|1973, independently of Znám, found all solutions to the improper problem for "k" ≤ 5. harvtxt|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.

Examples

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

:

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.

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:$sumfrac1\{x\_i\}\; +\; prodfrac1\{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:$sumfrac1\{x\_i\}\; +\; prodfrac1\{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. harvtxt|Brenton|Hill|1988 describe an application of the equation in topology, to the classification of singularities on surfaces, and harvtxt|Domaratzki|Ellul|Shallit|Wang|2005 describe an application to the theory of nondeterministic finite automata.

Number of solutions

As harvtxt|Janák|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 OEIS|id=A075441.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 (harvnb|Cao|Liu|Zhang|1987, harvnb|Sun|Cao|1988). harvtxt|Sun|Cao|1988 conjecture that the number of solutions for each value of "k" grows monotonically with "k".

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 harv|Butske|Jaje|Mayernik|2000; it is unknown whether infinitely many solutions of this type exist.

References

* citation
last = Barbeau | first = G. E. J.
title = Problem 179
journal = Canad. Math. Bull.
volume = 14
year = 1971
issue = 1
pages = 129

* citation
last = Brenton| first = Lawrence
last2 = Hill | first2 = Richard
title = On the Diophantine equation 1=&Sigma;1/"n"_"i" + 1/&Pi;"n"_"i" and a class of homologically trivial complex surface singularities
journal = Pacific Journal of Mathematics
url = http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102689567
volume = 133
issue = 1
year = 1988
pages = 41–67
id = MathSciNet | id = 0936356

* citation
last = Brenton| first = Lawrence
last2 = Vasiliu| first2 = Ana
title = Znám's problem
journal = Mathematics Magazine
volume = 75
pages = 3–11
year = 2002

* citation
last = Butske| first = William
last2= Jaje|first2= Lynda M.
last3 = Mayernik| first3 = Daniel R.
title = On the equation $scriptstylesum\_\{p|N\}frac\{1\}\{p\}+frac\{1\}\{N\}=1$, pseudoperfect numbers, and perfectly weighted graphs
journal = Mathematics of Computation
volume = 69
year = 2000
pages = 407–420
url = http://www.ams.org/mcom/2000-69-229/S0025-5718-99-01088-1/home.html
id = MathSciNet | id = 1648363

* citation
last = Cao |first= Zhen Fu
last2 = Jing| first2= Cheng Ming
title = On the number of solutions of Znám's problem
journal = J. Harbin Inst. Tech.
volume = 30
year = 1998
issue = 1
pages = 46–49
id = MathSciNet | id = 1651784

* citation
last = Cao| first = Zhen Fu
last2 = Liu| first2 = Rui
last3 = Zhang| first3= Liang Rui
title = On the equation $scriptstylesum^s\_\{j=1\}(1/x\_j)+(1/(x\_1cdots\; x\_s))=1$ and Znám's problem
journal = Journal of Number Theory
volume = 27
year = 1987
issue = 2
pages = 206–211
id = MathSciNet | id = 0909837
doi = 10.1016/0022-314X(87)90062-X

* citation
last = Domaratzki| first = Michael
last2 = Ellul | first2 = Keith
last3 = Shallit| first3 = Jeffrey
last4 = Wang| first4 = Ming-Wei
title = Non-uniqueness and radius of cyclic unary NFAs
journal = International Journal of Foundations of Computer Science
volume = 16
issue = 5
pages = 883–896
year = 2005
url = http://www.cs.umanitoba.ca/~mdomarat/pubs/DESW_dcfs.ps
id = MathSciNet | id = 2174328
doi = 10.1142/S0129054105003352

* citation
last = Janák| first = Jaroslav
last2= Skula| first2= Ladislav
title = On the integers $scriptstyle\; x\_\{i\}$ for which $scriptstyle\; x\_\{i\}|x\_\{1\}cdots\; x\_\{i-1\}x\_\{i+1\}cdots\; x\_\{n\}+1$
journal = Math. Slovaca
volume = 28
year = 1978
issue = 3
pages = 305–310
id = MathSciNet | id = 0534998

* citation
last = Mordell| first = L. J.
title = Systems of congruences.
journal = Canad. Math. Bull.
volume = 16
year = 1973
pages = 457–462
id = MathSciNet | id = 0332650
* citation
last = Skula| first= Ladislav
title = On a problem of Znám
format = Russian, Slovak summary
journal = Acta Fac. Rerum Natur. Univ. Comenian. Math.
volume = 32
year = 1975
pages = 87–90
id = MathSciNet | id = 0539862

* citation
last = Sun| first= Qi
title = On a problem of Š. Znám
journal = Sichuan Daxue Xuebao
year = 1983
issue = 4
pages = 9–12
id = MathSciNet | id = 0750288

* citation
last = Sun| first = Qi
last2= Cao| first2 = Zhen Fu
title = On the equation $scriptstylesum^s\_\{j=1\}1/x\_j+1/x\_1cdots\; x\_s=n$ and the number of solutions of Znám's problem
journal = Northeastern Mathematics Journal
volume = 4
year = 1988
issue = 1
pages = 43–48
id = MathSciNet | id = 0970644

External links

* cite web
author = Primefan
url = http://www.geocities.com/primefan/ZnamProbSols.html
title = Solutions to Znám's Problem

*