Block designs, permutation groups and prime values of polynomials

G. A. Jones ; A. K. Zvonkin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 1, pp. 233-253

Résumé

A recent construction by Amarra, Devillers and Praeger of block designs with specific parameters and large symmetry groups depends on certain quadratic polynomials, with integer coefficients, taking prime power values. Similarly, a recent construction by Hujdurović, Kutnar, Kuzma, Marušič, Miklavič and Orel of permutation groups with specific intersection densities depends on certain cyclotomic polynomials taking prime values. The Bunyakovsky Conjecture, if true, would imply that each of these polynomials takes infinitely many prime values, giving infinite families of block designs and permutation groups with the required properties. We have found large numbers of prime values of these polynomials, and the numbers found agree very closely with the estimates for them provided by Li's recent modification of the Bateman–Horn Conjecture. While this does not prove that these polynomials take infinitely many prime values, it provides strong evidence for this, and it also adds extra support for the validity of the Bunyakovsky and Bateman–Horn Conjectures.

Détail

Keywords: Block design, intersection density, prime number, Bateman–Horn Conjecture, Bunyakovsky Conjecture.
Mots-clés : permutation group, polynomial

Bibliographie

[1] Aletheia-Zomlefer S.L., Fukshansky L., and Garcia S.R., “The Bateman–Horn conjecture: heuristics, history, and applications”, Expo. Math., 38 (2020), 430–479 ; arXiv: 1807.08899v4 | DOI | MR | Zbl

[2] Amarra C., Devillers A. and Praeger C.E., “Delandsheer–Doyen parameters for block-transitive point-imprimitive block designs”, Designs, Codes and Cryptography, 90 (2022), 2205–2221 ; arXiv: 2009.00282 | DOI | MR | Zbl

[3] Banks W.D., Pappalardi F., and Shparlinski I.E., “On group structures realized by elliptic curves over arbitrary finite fields”, Exp. Math., 21:1 (2012), 11–25 | DOI | MR | Zbl

[4] Bateman P.T. and Horn R.A., “A heuristic asymptotic formula concerning the distribution of prime numbers”, Math. Comp., 16 (1962), 220–228 | DOI | MR

[5] Belabas K., Cohen H., Numerical Algorithms for Number Theory Using Pari/GP, All the programs used in the book may be downloaded via a link given on the page, Mathematical Surveys and Monographs, 254, AMS, 2021 URL: https://www.math.u-bordeaux.fr/~kbelabas/Numerical_Algorithms/ | DOI | MR | Zbl

[6] Borevich Z.I. and Shafarevich I.R., Number theory, Acad. Press, NY, 1966 | MR | Zbl

[7] Bouniakowsky V., “Sur les diviseurs numériques invariables des fonctions rationnelles entières”, Mém. Acad. Sci. St. Péteresbourg, $6^{\rm e}$ série, VI (1857), 305–329

[8] Boxall J. and Gruenewald D., “Heuristics on pairing-friendly abelian varieties”, LMS J. Comput. Math., 18:1 (2015), 419–443 | DOI | MR | Zbl

[9] Bunyakovsky conjecture, Wikipedia [e-resource] URL: https://en.wikipedia.org/wiki/Bunyakovsky_conjecture

[10] Carmichael numbers, Wikipedia [e-resource] URL: https://en.wikipedia.org/wiki/Carmichael_number

[11] Cohen H., High-precision computation of Hardy–Littlewood constants, [e-resource]. Preprint URL: https://oeis.org/A221712/a221712.pdf

[12] Cook J.D., Distribution of prime powers [e-resource], John D. Cook's blog URL: https://www.johndcook.com/blog/2018/09/03/counting-prime-powers

[13] Covanov S. and Thomé E., “Fast integer multiplication using generalized Fermat primes”, Math. Comp., 8 (2019), 1449–1477 | DOI | MR

[14] David C. and Smith E., “A Cohen–Lenstra phenomenon for elliptic curves”, J. London Math. Soc. (2), 89:1 (2014), 24–44 | DOI | MR | Zbl

[15] Delandtsheer A. and Doyen J., “Most block-transitive $t$-designs are point-primitive”, Geom. Dedicata, 29 (1989), 307–310 | DOI | MR | Zbl

[16] Ellis D., Kalai G., and Narayanan B., “On symmetric intersecting families”, European J. Combin., 86 (2020), 103094 | DOI | MR | Zbl

[17] Erdös P., Ko C., and Rado R., “Intersection theorems for systems of finite sets”, Q. J. Math., 12 (1961), 313–320 | DOI | MR | Zbl

[18] Euler L., Letter to Goldbach, 28th October 1752 (letter CXLIX) URL: ; “De numeris primis valde magnis”, Novi Commentarii academiae scientiarum Petropolitanae, 9 (1760), 99–153; Commentat. Arith., 1 (1849), 356–378; Opera Omnia: Ser. 1, 3, 1–45 http://eulerarchive.maa.org/correspondence/letters/OO0877.pdf | MR

[19] Fernández-Alcober G.A., Kwashira R., and Martínez L., “Cyclotomy over products of finite fields and combinatorial applications”, Europ. J. Comb., 31 (2010), 1520–1538 | DOI | MR | Zbl

[20] Hardy G.H. and Littlewood J.E., “Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes”, Acta Math., 114 (1923), 215–273 | MR

[21] Hujdurović A., Kutnar K., Kuzma B., Marušič D., Miklavič Š., and M. Orel, “On intersection density of transitive groups of degree a product of two odd primes”, Finite Fields Appl., 78 (2022), 101975 ; arXiv: 2107.09327 | DOI | MR

[22] Jacobson M.J., Jr. and Williams H.G., “New quadratic polynomials with high densities of prime values”, Math. Comp., 72:241 (2002), 499–519 | DOI | MR

[23] Jones G.A. and Jones J.M., Elementary Number Theory, Springer, NY, 1998 | MR | Zbl

[24] Jones G.A. and Zvonkin A.K., Klein's ten planar dessins of degree 11, and beyond, [e-resource], arXiv: 2104.12015

[25] Jones G.A. and Zvonkin A.K., “Groups of prime degree and the Bateman–Horn Conjecture”, Expo. Math., 2022 | DOI | MR

[26] Kim D., “Nonexistence of perfect 2-error-correcting Lee codes in certain dimensions”, European J. Combin., 63 (2017), 1–5 | DOI | MR

[27] Li W., “A note on the Bateman–Horn conjecture”, J. Number Theory, 208 (2020), 390–399 ; arXiv: 1906.03370 | DOI | MR | Zbl

[28] McEliece R.J., “Irreducible cyclic codes and Gauss sums”, Combinatorics, Part I: Theory of designs, finite geometry and coding theory (Proc. NATO Advanced Study Inst., Breukelen, 1974), Math. Centre Tracts, 55, Math. Centrum, Amsterdam, 1974, 179–196 | MR

[29] Meagher K., Razafimahatratra A.S., and Spiga P., “On triangles in derangement graphs”, J. Combin. Theory, Ser. A, 180 (2021), 105390 ; arXiv: 2009.01086 | DOI | MR | Zbl

[30] Mertens F., “Ein Beitrag zur analytischen Zahlentheorie”, J. reine angew. Math., 78 (1874), 46–62 | MR

[31] The Online Encyclopedia of Integer Sequences URL: https://oeis.org

[32] Rivin I., Some experiments on Bateman–Horn, 2015; arXiv: 1508.07821

[33] RSA numbers, Wikipedia [e-resource] URL: https://en.wikipedia.org/wiki/RSA_numbers

[34] Scholl T., “Isolated elliptic curves and the MOV attack”, J. Math. Cryptol., 11 (2017), 131–146 | DOI | MR | Zbl

[35] Scholl T., “Super-isolated elliptic curves and abelian surfaces in cryptography”, Exp. Math., 28 (2019), 385–397 | DOI | MR | Zbl

[36] Sha M., “Heuristics of the Cocks–Pinch method”, Adv. Math. Commun., 8 (2014), 103–118 | DOI | MR | Zbl

[37] Shanks D. and Lal M., “Bateman's constant reconsidered and the distribution of cubic residues”, Math. Comp., 26:117 (1972), 265–285 | MR | Zbl