Problema di Znám

Nella teoria dei numeri, il problema di Znám si chiede quali insiemi di $k$ interi hanno la proprietà che ogni elemento nell'insieme sia un divisore proprio del prodotto degli altri numeri, più 1. Il nome del problema deriva dal matematico slovacco Štefan Znám, che lo suggerì nel 1972, sebbene altri matematici abbiano considerato problemi simili nello stesso periodo. Un problema collegato fa cadere l'ipotesi di divisibilità propria, e in seguito sarà chiamato problema di Znám improprio.

Dimostrazione grafica che 1 = 1/2 + 1/3 + 1/11 + 1/23 + 1/31 + 1/(2×3×11×23×31). Ogni riga, composta con k quadrati di lato 1/k, ha area totale 1/k, e tutti insieme ricoprono esattamente un quadrato di area 1. L'ultima riga ha 47058 quadrati di lato 1/47058 e per questo troppo piccola da osservare nella figura.

Si costruisce facilmente una soluzione al problema di Znám improprio prendendo i primi $k$ termini della successione di Sylvester. Sun (1983) mostrò che esiste almeno una soluzione del problema di (proprio) per ogni $k\geq 5$. La soluzione di Sun si basa su una relazione di ricorrenza simile a quella della successione di Sylvester, ma con una differente scelta di valori iniziali.

Il problema di Znám è strettamente collegato alle frazioni egizie. Si sa che esistono solo un numero finito di soluzioni per ogni $k$ fissato, ma rimane ancora sconosciuto se esistono soluzioni al problema di Znám con solo numeri dispari, insieme a molte altre questioni aperte.

Il problema

Il problema di Znám si chiede quali insiemi di interi hanno la proprietà che ogni elemento nell'insieme sia un divisore proprio del prodotto degli altri numeri, più 1. Cioè, fissato $k$, quali insiemi di interi

$\{n_{1},\ldots ,n_{k}\}$

esistono tali che, per ogni $i$, $n_{i}$ divide ma non è uguale a

${\Bigl (}\prod _{j\neq i}^{n}n_{j}{\Bigr )}+1\quad ?$

Un problema strettamente collegato riguarda insiemi di interi in cui ogni elemento è un divisore, non necessariamente proprio, del prodotto degli altri interi più 1. Questo problema non sembra avere un nome in letteratura, e sarà qui indicato come problema di Znám improprio. Ogni soluzione del problema di Znám è anche soluzione della versione impropria, ma non vale necessariamente il contrario.

Storia

Il problema di Znám deve il suo nome al matematico slovacco Štefan Znám, che lo suggerì nel 1972. Barbeau (1971) pose il problema di Znám per $k=3$, e Mordell (1973), indipendentemente da Znám, trovò tutte le soluzioni al problema improprio per $k\leq 5$. Skula (1975) mostrò che il problema di Znám' non ha soluzione per $k<5$, e attribuì a J. Janák la scoperta della soluzione {2, 3, 11, 23, 31} per $k=5$.

Esempi

Una soluzione al caso $k=5$ è {2, 3, 7, 47, 395}. Qualche calcolo mostra che

3 × 7 × 47 × 395	+ 1 =	389866,		che è divisibile ma non uguale a 2,
2 × 7 × 47 × 395	+ 1 =	259911,		che è divisibile ma non uguale a 3,
2 × 3 × 47 × 395	+ 1 =	111391,		che è divisibile ma non uguale a 7,
2 × 3 × 7 × 395	+ 1 =	16591,		che è divisibile ma non uguale a 47, e
2 × 3 × 7 × 47	+ 1 =	1975,		che è divisibile ma non uguale a 395.

Un'interessante soluzione "mancata" per $k=4$ è l'insieme {2, 3, 7, 43}, formato dai primi quattro termini della successione di Sylvester. Possiede la proprietà che ogni intero divide il prodotto degli altri elementi nell'insieme più 1, ma l'ultimo numero è proprio uguale al prodotto più uno, invece di essere un divisore proprio. Di conseguenza, è una soluzione del problema di Znám improprio ma non di quello originale.

Connessione con le frazioni egizie

Ogni soluzione al problema di Znám improprio è equivalente (attraverso una divisione per il prodotto degli $x_{i}$) a risolvere l'equazione

$\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=y,$

dove $y$ e $x_{i}$ devono essere interi. Tuttavia, tutte le soluzioni conosciute hanno $y=1$, perciò soddisfano l'equazione

$\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=1.$

In altre parole, portano a una rappresentazione in frazioni egizie del numero 1, cioè come somme di frazioni unitarie. Molti degli articoli citati sul problema di Znám studiano anche le soluzioni di questa equazione. Brenton & Hill (1988) descrive un'applicazione dell'equazione in topologia, nella classificazione delle singolarità sulle superfici, e Domaratzki et al. (2005) espone l'applicazione alla teoria dell'automa a stati finiti non deterministico.

Numero di soluzioni

Come mostrò Janák & Skula (1978), il numero di soluzioni per $k$ fissato è finito k, quindi per ogni $k$ ha senso contare le soluzioni.

Brenton e Vasiliu calcolarono che il numero di soluzioni per piccoli valori di $k$, partendo da $k=5$, forma la sequenza

2, 5, 18, 96 (sequenza A075441 in OEIS).

Attualmente, si conoscono alcune soluzioni al caso $k=9$ e $k=10$, ma è ancora incerto quante soluzioni rimangono da scoprire per questi valori di $k$. Tuttavia, esistono infinite soluzione se $k$ non è fissato: Cao & Jing (1998) mostrò che ci sono almeno 39 soluzioni per ogni $k\geq 12$, migliorando i precedenti risultati di (Cao, Liu & Zhang (1987) e Sun & Cao (1988)). Sun & Cao (1988) congetturò che il numero di soluzioni per ciascun valore di $k$ crescesse monotonicamente con $k$.

Rimane sconosciuto se esistono delle soluzioni al problema di Znám's composte da solo numeri dispari. Tranne un'eccezione, tutte le soluzioni iniziano con il numero 2. Se tutti gli elementi di una soluzione del problema di Znám (proprio o improprio) sono numeri primi, il loro prodotto è un numero pseudoperfetto primario (Butske, Jaje & Mayernik (2000)); è ignoto se esistono infinite soluzioni di questo tipo.

Bibliografia

• G. E. J. Barbeau, Problem 179, in Canadian Mathematical Bulletin, vol. 14, n. 1, 1971, p. 129.
• Lawrence Brenton e Richard Hill, On the Diophantine equation 1=Σ1/n_i + 1/Πn_i and a class of homologically trivial complex surface singularities, in Pacific Journal of Mathematics, vol. 133, n. 1, 1988, pp. 41–67, DOI:10.2140/pjm.1988.133.41, MR 0936356.
• Lawrence Brenton e Ana Vasiliu, Znám's problem, in Mathematics Magazine, vol. 75, n. 1, 2002, pp. 3–11, DOI:10.2307/3219178, JSTOR 3219178.
• William Butske, Lynda M. Jaje e Daniel R. Mayernik, On the equation $\scriptstyle \sum _{p|N}{\frac {1}{p}}+{\frac {1}{N}}=1$, pseudoperfect numbers, and perfectly weighted graphs, in Mathematics of Computation, vol. 69, 2000, pp. 407–420, DOI:10.1090/S0025-5718-99-01088-1, MR 1648363.
• Zhen Fu Cao e Cheng Ming Jing, On the number of solutions of Znám's problem, in J. Harbin Inst. Tech., vol. 30, n. 1, 1998, pp. 46–49, MR 1651784.
• Zhen Fu Cao, Rui Liu e Liang Rui Zhang, On the equation $\scriptstyle \sum _{j=1}^{s}(1/x_{j})+(1/(x_{1}\cdots x_{s}))=1$ and Znám's problem, in Journal of Number Theory, vol. 27, n. 2, 1987, pp. 206–211, DOI:10.1016/0022-314X(87)90062-X, MR 0909837.
• Michael Domaratzki, Keith Ellul, Jeffrey Shallit e Ming-Wei Wang, Non-uniqueness and radius of cyclic unary NFAs (ps), in International Journal of Foundations of Computer Science, vol. 16, n. 5, 2005, pp. 883–896, DOI:10.1142/S0129054105003352, MR 2174328.
• Jaroslav Janák e Ladislav Skula, On the integers $\scriptstyle x_{i}$ for which $\scriptstyle x_{i}|x_{1}\cdots x_{i-1}x_{i+1}\cdots x_{n}+1$, in Math. Slovaca, vol. 28, n. 3, 1978, pp. 305–310, MR 0534998.
• L. J. Mordell, Systems of congruences, in Canadian Mathematical Bulletin, vol. 16, 1973, pp. 457–462, DOI:10.4153/CMB-1973-077-3, MR 0332650.
• Ladislav Skula, On a problem of Znám, in Acta Fac. Rerum Natur. Univ. Comenian. Math., vol. 32, 1975, pp. 87–90, MR 0539862.
• Qi Sun, On a problem of Š. Znám, in Sichuan Daxue Xuebao, n. 4, 1983, pp. 9–12, MR 0750288.
• Qi Sun e Zhen Fu Cao, On the equation $\scriptstyle \sum _{j=1}^{s}1/x_{j}+1/x_{1}\cdots x_{s}=n$ and the number of solutions of Znám's problem, in Northeastern Mathematics Journal, vol. 4, n. 1, 1988, pp. 43–48, MR 0970644.

Collegamenti esterni

• (EN) Eric W. Weisstein, Problema di Znám, su MathWorld, Wolfram Research.
• Primefan, Solutions to Znám's Problem, su primefan.tripod.com.