×

Shifted products that are coprime pure powers. (English) Zbl 1131.11013

Let \(A\) be a set of positive integers such that \(ab+1\) is a perfect power for all distinct elements \(a,~b\) of \(A\). In this paper, the authors show that if \(A\subset \{1,\ldots,N\}\) and if additionally the elements \(ab+1\) are coprime any two as \(a<b\) range through elements of \(A\), then the cardinality of \(A\) is bounded above by \(8000 \log N/\log\log N\). Under the \(abc\) conjecture, the authors are able to drop the coprimality conditions and show that the cardinality of \(A\) is \(O(\log\log N)\). The proofs use an interesting combination of results from extremal graph theory and elementary estimates from the prime number theory.
The results of this paper have already been improved since this paper appeared. C. L. Stewart removed the coprimality assumption and proved that the cardinality of \(A\) is \[ O((\log N)^{2/3}(\log\log N)^{1/3}). \]
His approach used, aside from extremal graph theory and elementary estimates involving prime numbers, also results from transcendental number theory such as lower bounds for linear forms in logarithms of algebraic numbers. Under the \(abc\) conjecture, the reviewer [see F. Luca, Glas. Mat., III. Ser. 40, No. 1, 13–20 (2005; Zbl 1123.11011)] showed that such sets \(A\) have uniformly bounded cardinalities.

MSC:

11B75 Other combinatorial number theory
11D99 Diophantine equations
05D10 Ramsey theory
05C38 Paths and cycles

Citations:

Zbl 1123.11011
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, A.; Davenport, H., The equations \(3 x^2 - 2 = y^2\) and \(8 x^2 - 7 = z^2\), Quart. J. Math. Oxford Ser. (2), 20, 129-137 (1969) · Zbl 0177.06802
[2] Bollobás, B., Extremal Graph Theory (1978), Academic Press: Academic Press London, New York · Zbl 0419.05031
[3] Bombieri, E.; Granville, A.; Pintz, J., Squares in arithmetic progressions, Duke Math. J., 66, 369-385 (1992) · Zbl 0771.11034
[4] Bombieri, E.; Zannier, U., A note on squares in arithmetic progressions II, Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. Rend. Lincei (9) Mat. Appl., 13, 2, 69-75 (2002) · Zbl 1072.11010
[5] Bondy, J. A.; Simonovits, M., Cycles of even length in graphs, J. Combin. Theory Ser. B, 16, 97-105 (1974) · Zbl 0283.05108
[6] Bugeaud, Y.; Dujella, A., On a problem of Diophantus for higher powers, Math. Proc. Cambridge Philos. Soc., 135, 1-10 (2003) · Zbl 1042.11019
[7] Y. Bugeaud, K. Gyarmati, On generalizations of a problem of Diophantus, preprint.; Y. Bugeaud, K. Gyarmati, On generalizations of a problem of Diophantus, preprint. · Zbl 1065.11015
[8] Dujella, A., An absolute bound for the size of Diophantine \(m\)-tuples, J. Number Theory, 89, 1, 126-150 (2001) · Zbl 1010.11019
[9] Dujella, A., There are only finitely many Diophantine quintuples, J. Reine Angew. Math., 566, 183-214 (2004) · Zbl 1037.11019
[10] A. Dujella, web page: http://www.math.hr/\( \sim;\); A. Dujella, web page: http://www.math.hr/\( \sim;\)
[11] Faudree, R. J.; Simonovits, M., On a class of degenerate extremal graph problems, Combinatorica, 3, 1, 83-93 (1983) · Zbl 0521.05037
[12] A. Granville, ABC; A. Granville, ABC · Zbl 0924.11018
[13] Granville, A.; Stark, H. M., abc implies no “Siegel zeros” for \(L\)-functions of characters with negative discriminant, Invent. Math., 139, 3, 509-523 (2000) · Zbl 0967.11033
[14] Granville, A.; Tucker, T. J., It’s as easy as abc, Notices Amer. Math. Soc., 49, 10, 1224-1231 (2002) · Zbl 1160.11318
[15] Guy, R. K., Unsolved Problems in Number Theory (1994), Springer: Springer Berlin · Zbl 0805.11001
[16] Gyarmati, K., On a problem of Diophantus, Acta Arith., 97, 53-65 (2001) · Zbl 0986.11016
[17] K. Gyarmati, Hatvány-, hatványteli és hatványmentes számok összegsorozatokban és multiplikatív struktúrákban (in Hungarian), (Powers, powerful and powerfree numbers in sumsets and multiplicative structures), Master Thesis, Eötvös Loránd University, 2001.; K. Gyarmati, Hatvány-, hatványteli és hatványmentes számok összegsorozatokban és multiplikatív struktúrákban (in Hungarian), (Powers, powerful and powerfree numbers in sumsets and multiplicative structures), Master Thesis, Eötvös Loránd University, 2001.
[18] Gyarmati, K.; Sárközy, A.; Stewart, C. L., On shifted products which are powers, Mathematika, 49, 227-230 (2002) · Zbl 1047.11029
[19] Lander, L. J.; Parkin, T. R.; Selfridge, J. L., A survey of equal sums of like powers, Math. Comput., 21, 446-459 (1967) · Zbl 0149.28803
[20] Masser, D. W., Open problems, (Chen, W. W.L., Proceedings of the Symposium Analytical Number Theory (1985), Imperial College: Imperial College London)
[21] Rivat, J.; Sárközy, A.; Stewart, C. L., Congruence properties of the \(\Omega \)-function on sumsets, Illinois J. Math., 43, 1-18 (1999) · Zbl 0926.11075
[22] Rosser, J. B.; Schoenfeld, L., Approximate formulas for some functions of prime numbers, Illinois J. Math., 6, 64-94 (1962) · Zbl 0122.05001
[23] Stewart, C. L.; Tijdeman, R., On the greatest prime factor of \((ab + 1)(ac + 1)(bc + 1)\), Acta Arith., 79, 93-101 (1997) · Zbl 0869.11072
[24] Turán, P., On an extremal problem in graph theory (Hungarian), Mat. Fiz. Lapok, 48, 436-452 (1941)
[25] Turán, P., On the theory of graphs, Collect. Math., 3, 19-30 (1954) · Zbl 0055.17004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.