×

Gauss sums and the maximum cliques in generalized Paley graphs of square order. (English) Zbl 1519.05195

Summary: Let \(\mathrm{GP}(q,d)\) be the \(d\)-Paley graph defined on the finite field \(\mathbb{F}_q\). It is notoriously difficult to improve the trivial upper bound \(\sqrt{q}\) on the clique number of \(\mathrm{GP}(q,d)\). In this paper, we investigate the connection between Gauss sums over a finite field and the maximum cliques of their corresponding generalized Paley graphs. We show that the trivial upper bound on the clique number of \(\mathrm{GP}(q,d)\) is tight if and only if \(d \mid (\sqrt{q}+1)\), which strengthens the previous related results by I. Broere et al. [Quaest. Math. 11, No. 1, 91–93 (1988; Zbl 0634.05030)] and C. Schneider and A. C. Silva [J. Algebra Appl. 14, No. 6, Article ID 1550088, 13 p. (2015; Zbl 1312.05055)]. We also obtain a new simple proof of L. Stickelberger’s theorem on evaluating semi-primitive Gauss sums [Math. Ann. 37, 321–367 (1890; JFM 22.0100.01)].

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C15 Coloring of graphs and hypergraphs
11T24 Other character sums and Gauss sums
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Aoki, On pure Gauss sums, Comment. Math. Univ. St. Pauli 61 (2012), no. 2, 133-165. · Zbl 1345.11061
[2] S. Asgarli, C.H. Yip, Van Lint-MacWilliams’ conjecture and maximum cliques in Cayley graphs over finite fields, arXiv:2106.01522 (2021).
[3] C. Bachoc, M. Matolcsi, I.Z. Ruzsa, Squares and difference sets in finite fields, Integers 13 (2013), Paper No. A77, 5 pp. · Zbl 1284.11030
[4] L.D. Baumert, R.J. McEliece, Weights of irreducible cyclic codes, Information and Control 20 (1972), 158-175. · Zbl 0239.94007
[5] L.D. Baumert, W.H. Mills, R.L. Ward, Uniform cyclotomy, J. Number Theory 14 (1982), no. 1, 67-82. · Zbl 0475.12026
[6] B.C. Berndt, R.J. Evans, K.S. Williams, Gauss and Jacobi Sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1998. · Zbl 0906.11001
[7] A. Blokhuis, On subsets of \(GF(q^2)\) with square differences, Nederl. Akad. Wetensch. Indag. Math. 46 (1984), no. 4, 369-372. · Zbl 0561.12009
[8] I. Broere, D. Döman, J.N. Ridley, The clique numbers and chromatic numbers of certain Paley graphs, Quaestiones Math., 11 (1988), 91-93. · Zbl 0634.05030
[9] L. Carlitz, The number of solutions of a particular equation in a finite field, Publ. Math. Debrecen 4 (1956), 379-383. · Zbl 0070.04002
[10] S. Chowla, On Gaussian sums, Proc. Nat. Acad. Sci. U.S.A. 48 (1962), 1127-1128. · Zbl 0114.02902
[11] F.R.K. Chung, Several generalizations of Weil sums, J. Number Theory 49 (1994), no. 1, 95-106. · Zbl 0807.11038
[12] S. Cohen, Clique numbers of Paley graphs, Quaestiones Math., 11 (1988), 225-231. · Zbl 0691.05051
[13] E. Croot, V. Lev, Open problems in additive combinatorics, Additive combinatorics, 207-233, CRM Proc. Lecture Notes, 43, Amer. Math. Soc., Providence, RI, 2007. · Zbl 1183.11005
[14] D. Di Benedetto, J. Solymosi, E. White, On the directions determined by a Cartesian product in an affine Galois plane, arXiv:2001.06994 (2020). To appear in Combinatorica. · Zbl 1499.51005
[15] P. Erdös, H.N. Shapiro, On the least primitive root of a prime, Pacific J. Math. 7 (1957), 861-865. · Zbl 0079.06304
[16] R.J. Evans, Generalizations of a theorem of Chowla on Gaussian sums, Houston J. Math. 3 (1977), no. 3, 343-349. · Zbl 0372.10028
[17] R.J. Evans, Pure Gauss sums over finite fields, Mathematika 28 (1981), no. 2, 239-248. · Zbl 0475.10032
[18] G. Exoo, Clique Numbers for Small Paley Graphs, http://cs.indstate.edu/ge/Paley/cliques.html.
[19] C. Godsil, K. Meagher, Erdös-Ko-Rado theorems: algebraic approaches, Cambridge Studies in Advanced Mathematics, 149, Cambridge University Press, Cambridge, 2016. · Zbl 1343.05002
[20] B. Green, Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica 25 (2005), no. 3, 307-326. · Zbl 1110.11009
[21] B. Hanson, G. Petridis, Refined estimates concerning sumsets contained in the roots of unity, Proc. Lond. Math. Soc. (3) 122 (2021), no. 3, 353-358. · Zbl 1497.11029
[22] G. Jones, Paley and the Paley graphs, Isomorphisms, Symmetry and Computations in Algebraic Graph Theory, Springer Proceedings in Mathematics & Statistics, vol 305, Springer, Cham, 155-183. · Zbl 1442.05229
[23] A.A. Karatsuba, Arithmetic problems in the theory of Dirichlet characters, Russian Math. Surveys 63 (2008), no. 4, 641-690. · Zbl 1230.11099
[24] R. Lidl, H. Niederreiter, Finite Fields, second edition, Encyclopedia of Mathematics and its Applications, 20, Cambridge University Press, Cambridge, 1997.
[25] T.K. Lim, C.E. Praeger, On generalized Paley graphs and their automorphism groups, Michigan Math. J. 58 (2009), no. 1, 293-308. · Zbl 1284.05175
[26] E. Maistrelli, D.B. Penman, Some colouring problems for Paley graphs, Discrete Math. 306 (2006), no. 1, 99-106. · Zbl 1085.05031
[27] K. Momihara, Pure Gauss sums and skew Hadamard difference sets, Finite Fields Appl. 77 (2022), Paper No. 101932, 30pp. · Zbl 1475.11215
[28] C. Schneider, A.C. Silva, Cliques and colorings in generalized Paley graphs and an approach to synchronization, J. Algebra Appl. 14 (2015), no. 6, 1550088, 13 pp. · Zbl 1312.05055
[29] L. Stickelberger, Ueber eine Verallgemeinerung der Kreistheilung, Math. Ann. 37 (1890), no. 3, 321-367. · JFM 22.0100.01
[30] P. Sziklai, On subsets of \(GF(q^2)\) with \(d\) th power differences, Discrete Math. 208/209 (1999), 547-555. · Zbl 0945.51004
[31] Q. Xiang, Cyclotomy, Gauss sums, difference sets and strongly regular Cayley graphs, Sequences and their applications-SETA 2012, 245-256. Lecture Notes in Comput. Sci., 7280, Springer, Heidelberg, 2012. · Zbl 1305.05027
[32] C.H. Yip, On the clique number of Paley graphs and generalized Paley graphs, MSc thesis, University of British Columbia (2021).
[33] C.H. Yip, On the directions determined by Cartesian products and the clique number of generalized Paley graphs, Integers 21 (2021), Paper No. A51, 31 pp. · Zbl 1470.05140
[34] C.H. Yip, On maximal cliques of Cayley graphs over fields, arXiv:2101.09652 (2021).
[35] C.H. Yip, On the clique number of Paley graphs of prime power order, Finite Fields Appl. 77 (2022), Paper No. 101930, 16pp. · Zbl 1495.11022
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.