Condensed Ricci Curvature on Paley Graphs and their Generalizations
Vincent Bonini Daniel Chamberlin Stephen Cook Parthiv Seetharaman Tri Tran


[2020]primary 52C99, 53B99; secondary 05C10, 05C81, 05C99


Beyond Model Interpretability: Socio-Structural Explanations in Machine Learning
    Atoosa Kasirzadeh
    September 9, 2024
================================================================================








§ ABSTRACT 
We explore properties of generalized Paley graphs and we extend a result of Lim and Praeger <cit.> by providing a more precise description of the connected components of disconnected generalized Paley graphs. This result leads to a new characterization of when generalized Paley graphs are disconnected. We also provide necessary and sufficient divisibility conditions for the multiplicative group of the prime subfield of certain finite fields to be contained in the multiplicative subgroup of nonzero k-th powers. This latter result plays a crucial role in our development of a sorting algorithm on generalized Paley graphs that exploits the vector space structure of finite fields to partition certain subsets of vertices  in a manner that decomposes the induced bipartite subgraph between them into complete balanced bipartite subgraphs. As a consequence, we establish a matching condition between these subsets of vertices that results in an explicit formula for the condensed Ricci curvature on certain Paley graphs and their generalizations. 









§ INTRODUCTION

Ollivier defined the coarse Ricci curvature of Markov chains on metric spaces in terms of the Wasserstein (or transport) distance of measures in <cit.>, providing a synthetic notion of Ricci curvature and a bridge between Riemannian geometry and probabilistic methods. The investigation of Ollivier's coarse Ricci curvature on graphs presents an interesting avenue for research and offers an accessible framework for quantifying local connectivity of graphs. Consequently, it has many practical and computational applications in artificial intelligence, network analysis, and data science (cf. <cit.>).

Much work has been done on various forms of the coarse Ricci curvature on graphs (cf. <cit.>). We consider a modified notion of Ollivier's coarse Ricci curvature on graphs introduced by Lin, Lu, and Yau in <cit.> that we refer to as the condensed Ricci curvature as in <cit.>. In particular, we study the condensed Ricci curvature on Paley graphs and their generalizations, which serve as models of pseudo-random graphs that encode algebraic relations between the elements of certain finite fields. Standard (or quadratic) Paley graphs (q,2) are constructed by taking the elements of finite fields of prime power order q=p^n ≡ 1  4 as vertices and defining edges between vertices that differ by squares. Generalized Paley graphs (q,k) are constructed in a similar manner by taking the elements of finite fields of prime power order q=p^n ≡ 1  2k as vertices and defining edges between vertices that differ by higher order k-th powers (see Section <ref>). The connections of Paley graphs and their generalizations to number theory, field theory, and other branches of mathematics adds to their mathematical interest and allows one to apply tools from number theory and algebra in their study.

Generalized Paley graphs (q,k) share some of the well-known properties of quadratic Paley graphs. Indeed, they are symmetric and q-1/k-regular but unlike quadratic Paley graphs they are not self-complementary and may be disconnected when k >2 (see Section <ref>). Our main results concerning the condensed Ricci curvature on generalized Paley graphs requires an understanding of their connectivity properties. In a study of the automorphism groups of generalized Paley graphs, it was shown in Theorem 2.2 of <cit.> that a generalized Paley graph (q,k) of order q=p^n is connected if and only if k is not a multiple of (q-1)/(p^a-1) for any proper divisor a of n. Moreover, if (q,k) is disconnected, then each connected component is isomorphic to the generalized Paley graph (p^a,k') where k'=k(p^a-1)/(q-1) ≥ 1 and a is some proper divisor of n such that (q-1)/(p^a-1) divides k.
 
From the divisibility conditions in this result of <cit.>, one finds that a generalized Paley graph 𝒫(q, k) is connected if and only if no proper subfield of _q contains the multiplicative subgroup of nonzero k-th powers. Hence, although it is not explicitly stated in <cit.>, it is natural to expect that each of the connected components of a disconnected generalized Paley graph 𝒫(q, k) is isomorphic to a generalized Paley graph defined over the smallest subfield of _q that contains the subgroup of nonzero k-th powers. Using basic properties of finite fields and finite cyclic groups, we provide a modest extension of this result of <cit.> by showing that each connected component of a disconnected generalized Paley graph is isomorphic to the generalized Paley graph (p^a,k') as described above, where a is in fact the smallest such proper divisor of n, or equivalently, where _p^a is the smallest subfield of _q containing the subgroup of nonzero k-th powers.  


Let k ≥ 2 and suppose that the generalized Paley graph 𝒫(q, k) of order q=p^n is disconnected. Then each connected component of 𝒫(q, k) is isomorphic to the generalized Paley graph 𝒫(p^a, k') with k' = k (p^a-1)/(q-1) ≥ 1 where a is the smallest proper divisor of n such that (q-1)/(p^a-1) divides k.


Now suppose that θ is a primitive element of the finite field _q of order q=p^n and let (_q^×)^k denote the multiplicative subgroup of nonzero k-th powers in _q^×. Noting that the smallest subfield of _q that contains (_q^×)^k is given by the field extension _p(θ^k), it follows that the parameter a in the results of <cit.> and Theorem <ref> is precisely the degree of this extension, or equivalently, the degree of the minimal polynomial of θ^k over _p. As a result of these observations, we have the following reformulation of the findings of <cit.> and Theorem <ref>, which provides a new characterization of when generalized Paley graphs are disconnected.


Let k ≥ 2 and suppose that θ is a primitive element of the finite field _q of order q=p^n with q ≡ 1  2k. Then the generalized Paley graph 𝒫(q, k) is disconnected if and only if the field extension _p(θ^k) is a proper subfield of _q. Furthermore, if 𝒫(q, k) is disconnected, then each connected component is isomorphic to the generalized Paley graph 𝒫(p^a, k') with  

    k' = |_p(θ^k)^×|/| (_q^×)^k |≥ 1

where a < n is the degree of the extension _p(θ^k) over _p.


In light of the aforementioned results of <cit.>, we also provide some cases of interest where we can guarantee that generalized Paley graphs are connected.


Let k ≥ 2 and suppose that q=p^n is a prime power such that q ≡ 1  2k. If k < p^n/2+1, then the generalized Paley graph (q,k) is connected.


As a consequence of Theorem <ref> and a straightforward calculus argument, we obtain the fact that all generalized Paley graphs (q,k) of order q=p^km are connected. 


Let m≥ 1, k ≥ 2 and suppose that q=p^km is a prime power such that q ≡ 1  2k. Then the generalized Paley graph 𝒫(q, k) is connected.  
 

We then turn our attention to the derivation of an explicit formula for the condensed Ricci curvature on Paley graphs and their generalizations. Given a connected, locally finite, undirected, simple graph G = (V, E) with shortest path distance function ρ:V × V →∪{0} and vertex v ∈ V, let

    Γ(v) = {w ∈ V |ρ(v,w)=1 }  = {w ∈ V | vw ∈ E  }

denote the subset of vertices that are adjacent v. Then for any edge xy ∈ E, one can decompose the neighbor sets Γ(x) and Γ(y) into disjoint unions

    Γ(x) = N_x ∪∇_xy∪{y}  and  Γ(y) = N_y ∪∇_xy∪{x}

as in <cit.>, where ∇_xy = Γ(x) ∩Γ(y) denotes the subset of vertices that are adjacent to both x and y and where

    N_x = Γ(x) ∖ (∇_xy∪{y})   and   N_y = Γ(y) ∖ (∇_xy∪{x}).

 
Understanding matchings between the neighbor sets N_x and N_y in a graph G is essential to the calculation of the condensed Ricci curvature (x, y) of an edge xy ∈ E. For example, in <cit.> it is shown that for any edge xy ∈ E of a strongly regular graph of degree d, the condensed Ricci curvature

    (x, y) = 1/d(2 + |∇_xy| - (|N_x| - m))

where m is the size of a maximum matching ℳ between N_x and N_y. In general, when a perfect matching exists between the neighbor sets N_x and N_y for every edge xy ∈ E, the graph G is said to satisfying the Global Matching Condition <cit.>. An explicit formula for the condensed Ricci curvature along edges in graphs that satisfy the Global Matching Condition is established in <cit.>.  We state a combined version of Lemma 6.2 and Theorem 6.3 of <cit.> below.

 
Let G=(V,E) be a connected, locally finite, undirected, simple graph satisfying the Global Matching Condition. Then G is regular of degree d and the condensed Ricci curvature

    (x,y) = 1/d(2 + |∇_xy|)

for any edge xy ∈ E. 


Our derivation of an explicit formula for the condensed Ricci curvature on generalized Paley graphs relies on establishing the Global Matching Condition and Theorem <ref>. We refer readers to Section 2 of <cit.> for the precise definition of the condensed Ricci curvature on graphs and our choice of terminology. The main ideas we use to establish the Global Matching Condition were first conceived for the special case of quadratic Paley graphs (q,2) of even power order q=p^2m in an unpublished student research project <cit.>. In particular, in <cit.> the fact that the multiplicative group of the corresponding prime subfield _p^× is contained in the subgroup of nonzero squares (_q^×)^2 led to the idea that the vector space structure of the finite field _q could be used to partition (or “sort”) the vertices in N_0 and N_1 in a way that a perfect matching could be easily obtained. Then, by the symmetry of quadratic Paley graphs, there is a perfect matching between the neighbor sets N_x and N_y for every edge xy ∈ E.

We found that the observations of <cit.> hold more broadly on certain generalized Paley graphs and that the induced bipartite subgraph of edges between vertices in N_x and N_y can actually be decomposed into complete balanced bipartite subgraphs with a “sorting algorithm” (see Section <ref>). With the aim of generalizing the ideas of <cit.>, we first establish a substantial case where the multiplicative group of the prime subfield _p^× of a finite field _q is contained in the subgroup of nonzero k-th powers (_q^×)^k.


Suppose p and k are prime. Then _p^×≤ (_p^km^×)^k for any positive integer m.


Moreover, as a simple consequence of the properties of finite cyclic groups, we have the following necessary and sufficient divisibility conditions for the multiplicative group of the prime subfield to be contained in the subgroup of nonzero k-th powers for the finite fields that serve as vertex sets of generalized Paley graphs.


Let k ≥ 2 and suppose that q=p^n is a prime power such that q ≡ 1  2k. Then _p^×≤ (_q^×)^k if and only if k |q-1/p-1.


Furthermore, as a straightforward consequence of Theorem <ref>, we find that if _q is a finite field of order q=p^n≡ 1  2k and k | p-1, then the multiplicative group of the prime subfield is contained in the subgroup of nonzero k-th powers if and only if n is a multiple of k. 


Let k ≥ 2 and suppose that q=p^n is a prime power such that q ≡ 1  2k. If k | p-1, then _p^×≤ (_q^×)^k if and only if n ≡ 0  k.


With Theorems <ref> and <ref> in hand, we then formally develop the sorting algorithm conceived in <cit.> and use it to establish the Global Matching Condition on connected generalized Paley graphs in which the multiplicative group of the corresponding prime subfield is contained in the subgroup of nonzero k-th powers (see Section <ref>).


Let k ≥ 2 and suppose (q,k) is a connected generalized Paley graph of order q=p^n. If _p^×≤ (_q^×)^k, then (q,k) satisfies the Global Matching Condition.


Due to Theorems <ref>, <ref>, <ref>, and <ref>, we then obtain the following generalization of the unpublished work of <cit.> on quadratic Paley graphs (q,2) of even power order q=p^2m.


Let m ≥ 1 and suppose that (q,k)=(V,E) is a generalized Paley graph of order q=p^km where k is prime. Then the condensed Ricci curvature

    (x,y) = k/q-1(2 + |∇_xy|)

for any edge xy ∈ E.  


More generally, as a consequence of Theorems <ref>, <ref>, and <ref>, we obtain the same explicit formula for the condensed Ricci curvature on generalized Paley graphs (q,k) of order q=p^n satisfying the divisibility condition k |q-1/p-1.


Let k ≥ 2 and suppose that (q,k)=(V,E) is a generalized Paley graph of order q=p^n where k |q-1/p-1. Then the condensed Ricci curvature

    (x,y) = k/q-1(2 + |∇_xy|)

for any edge xy ∈ E.  


We would like to point out that the formula for the condensed Ricci curvature in Theorem <ref> holds for both connected and disconnected generalized Paley graphs. However, in our work we consider these cases separately (see Theorems <ref> and <ref>) and we recover the same formula for the condensed Ricci curvature by applying our results for connected graphs to the connected components of disconnected generalized Paley graphs. In the special case that the connected components of a disconnected generalized Paley graph are complete graphs, we appeal to the following result stated in <cit.> and proved in <cit.>.


A connected, finite, undirected, simple graph G = (V, E) is complete if and only if the condensed Ricci curvature (x,y) > 1 for all vertices x,y ∈ V. In particular, if G is a complete graph on n vertices, then (x,y) =n/n-1 for all vertices x,y ∈ V. 


 Generalized Paley graphs (q,k) can be defined over finite fields of even order q=2^n as in <cit.>. In this case, one requires q ≡ 1  k rather than requiring q ≡ 1  2k as in the case for odd prime powers. Our work applies to generalized Paley graphs of even order, although some our results are trivial when considering finite fields of characteristic 2. However, for simplicity in presentation, we have chosen to focus on generalized Paley graphs of odd order.


This paper is organized as follows: In Section <ref> we formally define generalized Paley graphs and we discuss some of their relavant properties. In particular, we extend the results <cit.> by providing a more precise description of the connected components of disconnected generalized Paley graphs and we give a new characterization of when generalized Paley graphs are disconnected. In Section <ref> we establish results on the containment of the multiplicative group of the prime subfield of a finite field in the subgroup of nonzero k-th powers and we develop a “sorting algorithm”, which leads to establishing the Global Matching Condition and our explicit formulas for the condensed Ricci curvature on Paley graphs and their generalizations. 
 




 


§ ACKNOWLEDGEMENTS

This research was generously supported by the William and Linda Frost Fund in the Cal Poly Bailey College of Science and Mathematics. The authors would like to thank the referee for their careful reading of our work and their valuable input and insight. We also extend our gratitude to Professor Eric Brussel and Professor Rob Easton of Cal Poly for many vauble conversations. 








§ GENERALIZED PALEY GRAPHS AND THEIR PROPERTIES


In this section we introduce the definition of generalized Paley graphs and we discuss some of their relevant properties. Consider the finite field _q of order q=p^n and let _q^× denote the multiplicative group of _q. Then the set of nonzero squares in _q is denoted by

    (_q^×)^2 = {α∈_q^×|α = β^2   for some β∈_q^×}.

Paley graphs are then constructed by taking the field elements of certain finite fields as vertices and defining edges between those vertices that differ by squares.


Let q=p^n be a prime power such that q ≡ 1  4. Then the Paley graph of order q is defined to be the graph 𝒫(q)=(V,E) with vertex set V=_q and edge set E={xy | x-y ∈ (_q^×)^2}.


We refer to Paley graphs with edges between vertices that differ by squares as quadratic Paley graphs. It is known that quadratic Paley graphs are connected, self-complementary, strongly regular graphs with parameters (q, q-1/2, q-5/4, q-1/4) (cf. <cit.>). Naturally, one can generalize the definition of Paley graphs to define edges in terms of higher order powers. For integers k ≥ 2, we denote the set of nonzero k-th powers in _q by

    (_q^×)^k = {α∈_q^×|α = β^k   for some β∈_q^×}.



Let k ≥ 2 and suppose q=p^n is a prime power such that q ≡ 1  2k. Then the generalized Paley graph of order q with k-th powers is defined to be the graph 𝒫(q, k)=(V,E) with vertex set V=_q and edge set E={xy | x-y ∈ (_q^×)^k}.


Note that one can consider k=1 in (<ref>) and Definition <ref>. In this case the set of nonzero 1-st powers in _q is simply the multiplicative group _q^× and therefore (q,1)=K_q is the complete graph on q vertices. For simplicity in our presentation we will sometimes refer to complete graphs as generalized Paley graphs. For k=2, the generalized Paley graphs 𝒫(q,2) are quadratic Paley graphs as defined in Definition <ref>. It is natural to refer to generalized Paley graphs with k=3 as cubic, k=4 as quartic, k=5 as quintic, and so on. Throughout this work we refer to Paley graphs with edges between vertices that differ by k-th powers simply as generalized Paley graphs or k-Paley graphs. 

We also note that the set of nonzero k-th powers of a finite field _q form a subgroup of _q^×. Moreover, if θ is a generator for the multiplicative cyclic group _q^×, then θ^k generates the subgroup (_q^×)^k of k-th powers. Hence, since |θ| = q-1 and we are considering finite fields _q where k | q-1 , it follows that |θ^k | = q-1/k and therefore q-1/k elements of _q^× are k-th powers, or equivalently, the subgroup of nonzero k-th powers in _q^× has order q-1/k.
 
The condition q ≡ 1  2k in Definition <ref> ensures that q-1 is even, so q=p^n must be an odd prime power for the generalized Paley graphs under consideration. It also guarantees that generalized Paley graphs are undirected. In other words, the condition 2k | q-1 guarantees that if x-y ∈ (_q^×)^k for some x, y ∈_q, then y-x ∈ (_q^×)^k, or equivalently that -1 ∈ (_q^×)^k. Indeed, if θ is a generator for the multiplicative group _q^×, then
 
    1=(θ^q-1/2)^2

and therefore θ^q-1/2=-1. 
But then since q-1/2k∈, it follows that -1 = (θ^q-1/2k)^k ∈(_q^×)^k. 

Generalized Paley graphs retain some of the basic properties shared by quadratic Paley graphs. For example, generalized Paley graphs (q,k) are symmetric as they are easily seen to be arc-transitive under the subgroup of affine automorphims of the form x ↦ ax+b where a ∈ (_q^×)^k and b ∈_q. Moreover, k-Paley graphs are q-1/k-regular. For completeness, we record and prove these results in the following propositions.


Generalized Paley graphs 𝒫(q, k) = (V,E) of order q=p^n are symmetric. 



For any edges x_1y_1, x_2y_2 ∈ E, taking 
    a=(y_2-x_2)(y_1-x_1)^-1∈ (_q^×)^k   and  b = x_2 - a x_1 ∈_q^×,

it follows that the automorphism ϕ:V → V defined by ϕ(x) = ax+b satisfies ϕ(x_1) = x_2 and ϕ(y_1) = y_2. Thus, (q,k) is arc-transitive and therefore symmetric.



Generalized Paley graphs 𝒫(q, k) = (V,E) of order q=p^n are q-1/k-regular. 



Let θ be a generator for _q^× and suppose x ∈ V. Then for any other vertex y ∈ V, it follows that y ∈Γ(x) if and only if y-x ∈ (_q^×)^k. Hence, y ∈Γ(x) if and only if y = x+ (θ^k)^m for some m ∈. Thus, y ∈Γ(x) if and only if y ∈ x + ⟨θ^k ⟩, where x + ⟨θ^k ⟩ is the additive coset of the subgroup ⟨θ^k ⟩ of nonzero k-th powers. Noting that all cosets of ⟨θ^k ⟩ have order |θ^k | = q-1/k, we see that |Γ(x) | = q-1/k. Hence, since x was chosen arbitrarily, it follows that 𝒫(q, k) is q-1/k-regular.   


In contrast to the case for quadratic Paley graphs, generalized Paley graphs (q,k) are not self-complementary for k > 2. This follows directly from the fact that self-complementary graphs with q vertices must have q(q-1)/4 edges, that is, half the number of edges as in a complete graph on q vertices. But (q,k) is q-1/k-regular by Proposition <ref> and therefore has

    1/2· q ·q-1/k = q(q-1)/2k

edges, which is less than q(q-1)/4 for k>2. Furthermore, generalized Paley graphs (q,k) may not be connected when k > 2. However, even when a generalized Paley graph is disconnected, it turns out that each of its connected components is isomorphic to a single generalized Paley graph defined over a proper subfield of _q. These latter properties are due to Theorem 2.2 of <cit.>. We restate the relevant portions of this theorem in the context of our work below.


For k ≥ 2, the generalized Paley graph 𝒫(q, k) of order q=p^n is connected if and only if k is not a multiple of (q-1)/(p^a-1) for any proper divisor a of n. Furthermore, if 𝒫(q, k) is disconnected, then each connected component is isomorphic to the generalized Paley graph 𝒫(p^a, k') with k' = k (p^a-1)/(q-1) ≥ 1 where a is some proper divisor of n such that (q-1)/(p^a-1) divides k.
 

As noted in the introduction, the divisibility conditions in Theorem <ref> imply that a generalized Paley graph 𝒫(q, k) is connected if and only if no proper subfield of _q contains the subgroup of nonzero k-th powers. Indeed, since k | q-1, it follows that (q-1)/(p^a-1) divides k if and only if | (_q^×)^k | = q-1/k divides |_p^a^×| = p^a-1, or equivalently, (_q^×)^k≤_p^a^_×. Therefore, it is natural to expect that each of the connected components of a disconnected generalized Paley graph 𝒫(q, k) is isomorphic to a generalized Paley graph defined over the smallest subfield of _q that contains the subgroup of nonzero k-th powers. 

Now if q=p^n is a prime power such that q ≡ 1  2k and b is a proper divisor of n for which (q-1)/(p^b-1) divides k, then k = k'(q-1)/(p^b-1) for some k' ∈ so 

    p^b-1= k' q-1/k =2k' q-1/2k.

But q-1/2k∈ so by (<ref>) it follows that 2k' | p^b-1 and therefore p^b ≡ 1  2k'. Thus, one obtains a generalized Paley graph (p^b,k') over the proper subfield _p^b of _q for every proper divisor b of n for which (q-1)/(p^b-1) divides k. However, if b is not the smallest such divisor of n, that is if _p^b is not the smallest subfield of _q containing the subgroup of nonzero k-th powers, then it turns out that (p^b,k') is also disconnected.

Although it is not explicitly stated in <cit.>, a further analysis shows that each of the connected components of a disconnected generalized Paley graph (q,k) is actually isomorphic to the generalized Paley graph 𝒫(p^a, k') as described in Theorem <ref> where a is in fact the smallest proper divisor of n such that (q-1)/(p^a-1) divides k, or equivalently, where _p^a is the smallest subfield of _q containing the subgroup of nonzero k-th powers.


Let k ≥ 2 and suppose the generalized Paley graph 𝒫(q, k) of order q=p^n is disconnected. Then each connected component of 𝒫(q, k) is isomorphic to the generalized Paley graph 𝒫(p^a, k') with k' = k (p^a-1)/(q-1) ≥ 1 where a is the smallest proper divisor of n such that (q-1)/(p^a-1) divides k.



By Theorem <ref> we may assume that (q-1)/(p^b-1) divides k for some proper divisor b of n. Equivalently, since k | q-1, we may write this divisibility condition as q-1/k| p^b-1. Therefore, since _p^b^× is cyclic and | (_q^×)^k | = q-1/k divides |_p^b^×| = p^b-1, it follows that

    (_q^×)^k ≤_p^b^×.


Let a be the smallest proper divisor of n such that (q-1)/(p^a-1) divides k. If a < b, it follows that (_q^×)^k ≤_p^a^× as in (<ref>) and therefore

    (_q^×)^k ≤_p^a^×∩_p^b^× = _p^d^×

where d=gcd(a,b). Thus, by Lagrange's theorem, it follows from (<ref>) that q-1/k| p^d-1, or equivalently
(q-1)/(p^d-1) divides k where d=gcd(a,b) ≤ a is a proper divisor of n. But since a is the smallest proper divisor of n such that (q-1)/(p^a-1) divides k, it follows that a=d and therefore a | b.

Now let k'_a = k(p^a-1)/(q-1) and k'_b = k(p^b-1)/(q-1). Then

    k'_b= kp^b-1/q-1=k'_a q-1/p^a-1p^b-1/q-1 = k'_a p^b-1/p^a-1

and therefore (p^b-1)/(p^a-1) divides k'_b. Hence, since a is a proper divisor of b, it follows from Theorem <ref> that the generalized Paley graph (p^b,k'_b) is disconnected. Thus, in light of Theorem <ref>, the connected components of a disconnected generalized Paley graph (q,k) must be isomorphic to the generalized Paley graph (p^a,k') with k' = k (p^a-1)/(q-1) ≥ 1 where a is the smallest proper divisor of n such that (q-1)/(p^a-1) divides k, or equivalently, where _p^a is the smallest subfield of _q containing the subgroup of nonzero k-th powers.


Now suppose that θ is a primitive element of the finite field _q of order q=p^n with q ≡ 1  2k. Then the smallest subfield of _q that contains the subgroup of nonzero k-th powers is given by the field extension _p(θ^k) over _p. Thus, if the degree of this extension is strictly less than n, say

    [_p(θ^k):_p] = a < n,

it follows that _p(θ^k) = _p^a is a proper subfield of _q where a is the smallest proper divisor of n such that | (_q^×)^k | = q-1/k divides |_p(θ^k)^×| = p^a-1, or equivalently, such that (q-1)/(p^a-1) divides k. As a result of these observations, we see that the parameter a in Theorem 2.5 of <cit.> and Theorem 2.6 is precisely the degree of the field extension _p(θ^k) over _p, or equivalently, the degree of the minimal polynomial of θ^k over _p. Therefore, we have the following reformulation of the results of <cit.> and Theorem 2.6.


Let k ≥ 2 and suppose that θ is a primitive element of the finite field _q of order q=p^n with q ≡ 1  2k. Then the generalized Paley graph 𝒫(q, k) is disconnected if and only if the field extension _p(θ^k) is a proper subfield of _q. Furthermore, if 𝒫(q, k) is disconnected, then each connected component is isomorphic to the generalized Paley graph 𝒫(p^a, k') with

    k' = |_p(θ^k)^×|/| (_q^×)^k |≥ 1

where a < n is the degree of the extension _p(θ^k) over _p.


With these facts in hand, we focus our attention on connected generalized Paley graphs as our results will easily lend themselves to the connected components of disconnected generalized Paley graphs. One simple case where we can guarantee that generalized Paley graphs are connected is given in the following theorem.


Let k ≥ 2 and suppose that q=p^n is a prime power such that q ≡ 1  2k. If k < p^n/2+1, then the generalized Paley graph (q,k) of order q=p^n is connected.



Suppose that a is a proper divisor of n. Then

    p^n-1/p^a-1≥p^n-1/p^n/2-1 = p^n/2+1 > k.

Hence, k is not a multiple of (p^n-1)/(p^a-1) for any proper divisor a of n and therefore 𝒫(q, k) is connected by Theorem <ref>.


To conclude this section we present another special case where the generalized Paley graphs under consideration are connected. In particular, we show that all generalized Paley graphs (q,k) of order q=p^km are connected. This result contributes to a complete generalization of the observations outlined in <cit.> for quadratic Paley graphs (q,2) of even power order q=p^2m.


Let m≥ 1, k ≥ 2 and suppose that q=p^km is a prime power such that q ≡ 1  2k. Then the generalized Paley graph 𝒫(q, k) of order q=p^km is connected. 



It suffices to show that km > 2log_p(k-1) since then p^km/2+1 > k and therefore 𝒫(q, k) is connected by Theorem <ref>. To this end, consider the function f:(1,∞) → defined by

    f(x) = x - 2log_2(x-1) = x - 2/ln 2ln(x-1).

Then

    f'(x) = 1 - 2/(ln2)(x-1)

so f has a single critical point at 

    x^* = 2/ln2+1

where f'<0 on (1,x^*) and f'>0 on (x^*,∞). Thus, f is decreasing on (1,x^*) and increasing on (x^*,∞). Moreover, since 

    f(x^*) = 2/ln2(1-ln(2/ln2))+1 > 0,

it follows that f has a positive global minimum at x^*. Hence, f > 0 on (1,∞) and therefore x > 2log_2(x-1) for all x ∈ (1,∞). In particular, since k ≥ 2 and p is necessarily an odd prime, we see

    km ≥ k > 2log_2(k-1) > 2log_p(k-1)

and the desired result follows.









§ THE SORTING ALGORITHM AND THE GLOBAL MATCHING CONDITION

In this section we establish the Global Matching Condition for certain Paley graphs and their generalizations. As a consequence of Theorem <ref> of <cit.> we then obtain an explicit formula for the condensed Ricci curvature along the edges of these graphs. Consider a connected generalized Paley graph (q,k) of order q=p^n with vertex set V = _q and edge set E = {xy | x-y ∈ (_q^×)^k}. Due to the symmetry of generalized Paley graphs we may focus on the edge 01 ∈ E and the neighbor sets 

    N_0 = Γ(0) ∖ (∇_01∪{1})   and   N_1 = Γ(1) ∖ (∇_01∪{0})
 
as introduced in Section <ref>. 

Let H denote the induced bipartite subgraph consisting of all edges in E between vertices in N_0 and N_1. Our strategy in establishing the Global Matching Condition on the generalized Paley graphs under consideration is to formally develop and generalize the sorting algorithm that was first conceived in <cit.> for the special case of quadratic Paley graphs. We then apply this sorting algorithm to decompose the bipartite subgraph H into complete balanced bipartite subgraphs. Then one can pairwise match vertices in these subgraphs to construct a perfect matching between N_0 and N_1 and appeal to the symmetry of generalized Paley graphs to realize a perfect matching between the neighbor sets N_x and N_y for every edge xy ∈ E. 

On generalized Paley graphs the containment of the corresponding multiplicative group of the prime subfield in the subgroup of nonzero k-th powers plays a crucial role in the success of the sorting algorithm. With the aim of establishing an important case of this critical component of the sorting algorithm, we first present a special case of Theorem 9.1 in chapter 6, section 9 of <cit.>.


Let _p denote the field of prime order p and suppose k is prime. Let α∈_p^× and suppose that α∉(_p^×)^k. Then x^k - α is irreducible in _p[x].  


For the case of quadratic Paley graphs (q,2) of even power order q=p^2m, it was observed in <cit.> that the corresponding multiplicative group of the prime subfield _p^× is contained in the subgroup of nonzero squares (_q^×)^2. We appeal to Theorem <ref> to establish a more general version of this observation. 


Suppose p and k are prime. Then _p^×≤ (_p^km^×)^k for any positive integer m.



Let α∈_p^× and suppose that α∉(_p^×)^k. Then by Theorem <ref>, f(x) = x^k-α is irreducible in _p[x]. Therefore, if θ is a root of f, then

    _p[x] ⟨ x^k-α⟩≅_p(θ) ≅_p^k.
 

Now suppose that φ:_p(θ) →_p^k is an isomorphism. Noting that φ(α)=α since α∈_p, it follows that

    φ(θ)^k - α = φ(θ^k) - φ(α) = φ(θ^k - α) = φ(f(θ)) = φ(0) = 0.

Thus, α = φ(θ)^k ∈ (_p^k^×)^k and therefore since _p^k⊆_p^km for any positive integer m, it follows that α∈ (_p^km^×)^k. Hence, _p^×≤ (_p^km^×)^k as desired. 


Now suppose _q is a finite field of order q=p^n such that q ≡ 1  2k with k ≥ 2. As a simple consequence of the properties of finite cyclic groups, we have the following necessary and sufficient divisibility conditions for the multiplicative group of the prime subfield of _q to be contained in the subgroup of nonzero k-th powers.


Let k ≥ 2 and suppose that q=p^n is a prime power such that q ≡ 1  2k. Then _p^×≤ (_q^×)^k if and only if k |q-1/p-1.



Let _q be a finite field of order q=p^n such that q ≡ 1  2k. Then since

    |_p^×| = p-1   and  | (_q^×)^k | = q-1/k,

it follows from properties of finite cyclic groups and Lagrange's theorem that _p^×≤ (_q^×)^k if and only if p-1 |q-1/k, or equivalently k |q-1/p-1.


Clearly, since we are considering generalized Paley graphs (q,k) of order q=p^n where q ≡ 1  2k, it follows that k | q-1. 
Due to Theorem <ref>, it turns out that when k also divides p-1, the multiplicative group of the corresponding prime subfield _p^× is contained in the subgroup of nonzero k-th powers (_q^×)^k if and only if n is a multiple of k.


Let k ≥ 2 and suppose that q=p^n is a prime power such that q ≡ 1  2k. If k | p-1, then _p^×≤ (_q^×)^k if and only if n ≡ 0  k.



By Theorem <ref>, _p^×≤ (_q^×)^k if and only if k |q-1/p-1.
Hence, _p^×≤ (_q^×)^k if and only if

    q-1/p-1 = p^n-1 + p^n-2 + ⋯ + p + 1 ≡ 0  k.

But k | p-1 so p ≡ 1  k and therefore

    q-1/p-1 = p^n-1 + p^n-2 + ⋯ + p + 1 ≡ n  k.

Hence, by (<ref>) and (<ref>) it follows that _p^×≤ (_q^×)^k if and only if n ≡ 0  k.


Now that we have a better understanding of when the multiplicative group of the prime subfield is contained in the subgroup of nonzero k-th powers of a given finite field, we develop the sorting algorithm that we will use to construct a perfect matching between the neighbor sets N_0 and N_1 in a generalized Paley graph. To this end, let θ be a generator of the multiplicative group _q^× of the finite field _q of order q=p^n. Consider the minimal polynomial f ∈_p[x] of θ such that 

    _q ≅_p(θ) ≅_p[x] ⟨ f(x) ⟩.

In light of the isomorphisms in (<ref>), it follows that 1, θ, θ^2,…,θ^n-1 is a basis for _q as a vector space over _p and therefore 

    _q = { a_0 +  a_1θ + a_2 θ^2 + ⋯ + a_n-1θ^n-1| a_0, a_1,…,a_n-1∈_p}.


Our formalization of the sorting algorithm and substantiation of a perfect matching between the neighbor sets N_0 and N_1 relies on the following fact that was first observed for quadratic Paley graphs in <cit.>.
 

Let (q,k) be a connected generalized Paley graph of order q=p^n and suppose that θ is a generator of the multiplicative group _q^×. Fix a_1,…, a_n-1∈_p not all zero and set

    S=S(a_1,…,a_n-1)={ b + a_1θ + a_2 θ^2 + ⋯ + a_n-1θ^n-1| b∈_p}.
 
Then | N_0 ∩ S | = | N_1 ∩ S |.



First note that x ∈Γ(0) if and only if x ∈ (_q^×)^k if and only if x+1 ∈Γ(1) and therefore 

    |Γ(0) ∩ S | = |Γ(1) ∩ S |.

Now since a_1,…, a_n-1∈_p are not all zero, it follows that

    {0}∩ S = ∅  and  {1}∩ S = ∅.

Moreover, since

    Γ(0) = {1}∪ N_0 ∪∇_01  and  Γ(1) = {0}∪ N_1 ∪∇_01

are disjoint unions, it follows that

    |Γ(0) ∩ S | = | N_0 ∩ S | + |∇_01∩ S |

and

    |Γ(1) ∩ S | = | N_1 ∩ S | + |∇_01∩ S |.

Thus, by (<ref>) we may equate equations (<ref>) and (<ref>) to find | N_0 ∩ S | = | N_1 ∩ S | . 


Lemma <ref> provides an avenue for partitioning the neighbor sets N_0 and N_1 of a generalized Paley graph (q,k) by grouping vertices (or elements) in N_0 and N_1 with the same coefficients of θ,…,θ^n-1. In particular, when the nonzero elements of the prime subfield are all k-th powers, we can partition the induced bipartite subgraph H consisting of all edges in E between N_0 and N_1 into complete balanced bipartite subgraphs. By matching vertices in each of these complete subgraphs in pairwise fashion, we obtain a perfect matching between N_0 and N_1, which by symmetry shows that the generalized Paley graphs under consideration satisfy the Global Matching Condition. This approach is based on ideas from <cit.> where the argument was outlined for quadratic Paley graphs of even power order q=p^2m.


Let k ≥ 2 and suppose (q,k) is a connected generalized Paley graph of order q=p^n. If _p^×≤ (_q^×)^k, then (q,k) satisfies the Global Matching Condition.



By symmetry it suffices to consider the edge 01 ∈ E and to show that there is a perfect matching between N_0 and N_1.  As in Lemma <ref>, fix a_1,…, a_n-1∈_p not all zero and set 

    S(a_1,…,a_n-1) = { b + a_1θ + a_2 θ^2 + ⋯ + a_n-1θ^n-1| b∈_p}.
 
Then for any α∈ N_0 ∩ S(a_1,…,a_n-1), β∈ N_1 ∩ S(a_1,…,a_n-1), it follows that 

    α - β∈_p^×≤ (_q^×)^k.
   
Hence, αβ∈ E and therefore the bipartite subgraph H(a_1,…,a_n-1) consisting of all edges in E between N_0 ∩ S(a_1,…,a_n-1) and N_1 ∩ S(a_1,…,a_n-1) is complete. 
In light of Lemma <ref>, it follows that that the complete bipartite subgraph H(a_1,…,a_n-1) is balanced. Thus, we can match vertices in H(a_1,…,a_n-1) in a pairwise fashion to obtain a perfect matching between N_0 ∩ S(a_1,…,a_n-1) and N_1 ∩ S(a_1,…,a_n-1).

Now let a=(a_1,…,a_n-1) ∈_p^n-1 be a multi-index for a_1,…,a_n-1∈_p so that S(a) = S(a_1,…,a_n-1). Set 𝒮 = {S(a) | a ≠ 0 ∈_p^n-1} and let 𝒥 be a multi-indexing set for 𝒮. Noting that _p^×≤ (_q^×)^k implies _p ⊆{0}∪{1}∪∇_01, it follows that

    ⋃_a ∈𝒥 N_0 ∩ S(a) =  N_0 ∩⋃_a ∈𝒥 S(a) = N_0 ∩(_q ∖_p) = N_0

and similarly

    ⋃_a ∈𝒥 N_1 ∩ S(a) = N_1.

Therefore, since the sets S(a)=S(a_1,…,a_n-1) are disjoint for each distinct choice of a=(a_1,…,a_n-1) ∈𝒥, it follows from (<ref>) and (<ref>) that the bipartite subgraph H between N_0 and N_1 can be partitioned into complete balanced bipartite subgraphs H(a)=H(a_1,…,a_n-1) consisting of all edges in E between N_0 ∩ S(a) and N_1 ∩ S(a). Thus, since each subgraph H(a) admits a perfect matching, it follows that there is a perfect matching between N_0 and N_1 and therefore (q,k) satisfies the Global Matching Condition by symmetry. 
 
 
Due to Theorems <ref>, <ref>, <ref>, and <ref>, we obtain the following generalization of the unpublished work of <cit.> on quadratic Paley graphs (q,2) of even power order q=p^2m.


Let m ≥ 1 and suppose that (q,k)=(V,E) is a generalized Paley graph of order q=p^km  where k is prime. Then the condensed Ricci curvature

    (x,y) = k/q-1(2 + |∇_xy|)

for any edge xy ∈ E.  



First note that since (q,k) is a generalized Paley graph of order q=p^km with k ≥ 2, it follows that (q,k) is connected by Theorem <ref>. Moreover, since k is prime it follows that _p^×≤ (_q^×)^k by Theorem <ref>. Hence, from Theorem <ref> we see that (q,k) satisfies the Global Matching Condition so that the condensed Ricci curvature

    (x,y) = k/q-1(2 + |∇_xy|)

for any edge xy ∈ E by Theorem <ref>.  


Furthermore, as a consequence of Theorems <ref>, <ref>, and <ref>, we obtain the same explicit formula for the condensed Ricci curvature on a large class of connected generalized Paley graphs.


Let k ≥ 2 and suppose that (q,k)=(V,E) is a connected generalized Paley graph of order q=p^n where k |q-1/p-1. Then the condensed Ricci curvature

    (x,y) = k/q-1(2 + |∇_xy|)

for any edge xy ∈ E. 



Since k |q-1/p-1 it follows that _p^×≤ (_q^×)^k from Theorem <ref>. Hence, (q,k) satisfies the Global Matching Condition by Theorem <ref>. Therefore, since (q,k) is connected, it follows from Theorem <ref> that the condensed Ricci curvature

    (x,y) = k/q-1(2 + |∇_xy|)

for any edge xy ∈ E.


On the other hand, when a generalized Paley graph (q,k) with k |q-1/p-1 is disconnected, our work can be adapted to its connected components to recover the same formula as in Theorem <ref> for the condensed Ricci curvature.


Let k ≥ 2 and suppose that (q,k)=(V,E) is a disconnected generalized Paley graph order q=p^n where k |q-1/p-1. Then the condensed Ricci curvature

    (x,y) = k/q-1(2 + |∇_xy|)

for any edge xy ∈ E.


 From Theorems <ref> and <ref>, it follows that each of the connected components of (q,k) is isomorphic to the generalized Paley graph (p^a,k') with k'=k(p^a-1)/(q-1) ≥ 1 where a is the smallest proper divisor of n such that (q-1)/(p^a-1) divides k. Recalling that the divisibility condition k |q-1/p-1 is equivalent to p-1 |q-1/k, it follows that

    p-1 |q-1/k = p^a-1/k' = | (_p^a^×)^k'|

and therefore _p^×≤ (_p^a^×)^k' since (_p^a^×)^k' is a finite cyclic group. So for k' > 1, applying Theorems <ref> and <ref> to the connected components of (q,k) and noting the fact that k'=k(p^a-1)/(q-1), we see that the condensed Ricci curvature 

    (x,y) = k'/p^a-1(2 + |∇_xy|) = k/q-1(2 + |∇_xy|)

for any edge xy ∈ E.

In the special case that k'=1, we recall that the subgroup of nonzero 1-st powers in _p^a is simply the multiplicative group _p^a^×. Therefore, each connected component of the disconnected generalized Paley graph (q,k) is isomorphic to the complete graph (p^a,1) = K_p^a on p^a vertices. Thus, since the complete graph K_p^a=(V,E) on p^a vertices is regular of degree p^a-1, it follows for any edge xy ∈ E that ∇_xy = V ∖ ({x}∪{y}). Hence, |∇_xy| = p^a-2 and by Theorem <ref> we recover the formula 

    (x,y) = p^a/p^a-1 = 1/p^a-1(2 + |∇_xy|)=k/q-1(2 + |∇_xy|)

for the condensed Ricci curvature of any edge xy ∈ E.







plain







