Given a prime \( p \), a \( p \)-smooth integer is an integer whose prime factors are all at most \( p \). Let \( S_p \) be the multiplicative subgroup of \( \mathbb{Q} \) generated by \(-1\) and the \( p \)-smooth integers. Define the \( p \)-smooth partial field as \( \mathbb{S}_p = (\mathbb{Q}, S_p) \). Let \( g \) be the golden ratio \( (1+\sqrt{5})/2 \). Let \( G_p \) to be the multiplicative subgroup of \( \mathbb{R} \) generated by \( g \), \(-1\), and the \( p \)-smooth integers. Define the \( p \)-golden partial field as \( \mathbb{G}_p = (\mathbb{R}, G_p) \). The partial field \( \mathbb{S}_2 \) is actually the well-known dyadic partial field and \( \mathbb{S}_3 \) has sometimes been called the Gersonides partial field. We calculate the fundamental elements of \( \mathbb{S}_5 \), \( \mathbb{G}_2 \), \( \mathbb{G}_3 \), and \( \mathbb{G}_5 \).
Our proofs make use of the SageMath computational package.
The introduction of this paper assumes that the reader is familiar with matroid theory and linear optimization; however, these subjects are only necessary for motivating our study. The remainder of the paper is readable for any mathematically literate person.
A partial field \(\mathbb{P}\) is a pair \((R,G)\) in which \(R\) is a unitary ring (in this paper \(R\) will also be assumed to be commutative) and a subgroup \(G\) of the multiplicative group of units of \(R\) for which \(-1\in G\). A matrix \(A\) is a \(\mathbb{P}\)-matrix when every non-zero sub-determinant of \(A\) is in \(G\). One of the first widely studied examples of such matrices are totally unimodular matrices which are \(\mathbb{U}_{0}\)-matrices with \(\mathbb{U}_{0}=\left(\mathbb{Q},\{+1,-1\}\right)\). Consider the polyhedron \(A\mathbf{x}\leq\mathbf{b}\) in which \(\mathbf{b}\) is any integral vector. Hoffman and Kruskal [3] showed that every vertex of this polyhedron is integral for any \(\mathbf{b}\) if and only if \(A\) is totally unimodular. This implies that linear optimization and integer optimization are equivalent precisely when \(A\) is totally unimodular. This is highly significant in that integer optimization is NP-hard in general while linear optimization is quasi-polynomial (and is widely conjectured to be polynomial).
More recently studies concerning partial fields and \(\mathbb{P}\)-matrices have proliferated; in particular, within the field of matroid theory. Included among the many highly influential works are those of Tutte [15], Seymour [12], Lee [4, 5], Whittle [17, 18], and Pendavingh and Van Zwam [9, 10].
One thread of investigations concerns the relationship between the matroids which are both orientable and representable over some finite field. The dyadic partial field is \(\mathbb{D} = (\mathbb{Q}, \{\pm 2^{i}: i \in \mathbb{Z}\})\) and the golden-mean partial field is \(\mathbb{G} = \{\mathbb{R}, \{\pm g^{i}: i \in \mathbb{Z}\}\}\) in which \(g\) is the golden ratio \(\frac{1+\sqrt{5}}{2}\). A matroid \(M\) is \(\mathbb{P}\)-representable when there is a \(\mathbb{P}\)-matrix \(A\) for which \(M = M(A)\).
While Theorems 1.1 and 1.2 tell us that the relatively simple partial fields \(\mathbb{U}_{0}\) and \(\mathbb{D}\) completely describe all orientations of \(GF(2)\)- and \(GF(3)\)-representable matroids, Theorem 1.3 reveals that \(GF(4)\)-representable matroids have enough complexity so that a simple partial field like \(\mathbb{G}\) is not enough to describe all orientations. This leaves us with two obvious questions. One, how might we describe the remaining orientations of \(GF(4)\)-representable matroids? Two, what about orientations of \(GF(q)\)-representable matroids for \(q > 4\)?
Since \(\mathbb{R}\)-representable matroids are a proper subset of orientable matroids, partial fields \(\mathbb{P} = (R, G)\) in which \(R \leq \mathbb{R}\) are naturally of importance in analyzing matroids which are both orientable and \(GF(q)\)-representable. In order to utilize any given partial field \(\mathbb{P}\) (for example, to prove results of the above type) it is necessary to know what are the fundamental elements of a \(\mathbb{P}\). The elements of \(\mathbb{P}\) are just the elements of \(G \cup \{0\}\). An element \(f \in \mathbb{P}\) is fundamental when \(1 – f \in \mathbb{P}\). A fundamental element is trivial when \(f \in \{0, 1\}\). In this paper we will define and calculate the fundamental elements of one rational partial field and three new real partial fields. Aside from the possible utility of these partial fields, we feel this study is also appealing in that we utilize several rather old and interesting results from number theory.
Many of our proofs rely on computer calculations. We do these calculations in SageMath version 9.3 installed on a personal computer running the Windows-11 operating system. The code and output of our calculations are contained in the unpublished technical report [13].
A partial field \(\mathbb{P}\) is a pair \((R, G)\) in which \(R\) is a unitary ring (in this paper \(R\) will also be assumed to be commutative) and a subgroup \(G\) of the multiplicative group of units of \(R\) for which \(-1 \in G\). A matrix \(A\) is a \(\mathbb{P}\)-matrix when every non-zero subdeterminant of \(A\) is in \(G\).
The elements of a partial field \(\mathbb{P} = (R, G)\) are just the elements of \(G \cup \{0\}\). A fundamental element of \(\mathbb{P}\) is an element \(a\) for which \(1 – a \in G\). A fundamental element \(a\) is trivial when \(a = 0\) or \(1\). If \(a\) is a non-trivial fundamental element of \(\mathbb{P}\), then its associates are the elements of the set
The relation of being associates is an equivalence relation on the set of non-trivial fundamental elements of \(\mathbb{P}\). Thus it is customary to describe the set of fundamental elements of \(\mathbb{P}\) by a set of representatives from each equivalence class.
Some examples of partial fields are the following. The dyadic partial field is \(\mathbb{D} = (\mathbb{Q}, \{ \pm 2^i : i \in \mathbb{Z} \})\). It is easy to show that the non-trivial fundamental elements of \(\mathbb{D}\) are \(Assoc(2) = \{-1, \frac{1}{2}, 2\}\). The Gersonides partial field is \(\mathbb{GE} = (\mathbb{Q}, \{ \pm 2^i 3^j : i, j \in \mathbb{Z} \})\). Gersonides’ Theorem can be used to show [16, Lemma 2.5.40] that the non-trivial fundamental elements of \(\mathbb{GE}\) are \(Assoc(2) \cup Assoc(3) \cup Assoc(4) \cup Assoc(9)\).
Let \( p \) be a prime. A \( p \)-smooth integer is an integer whose largest prime factor is at most \( p \). Pairs of consecutive \( p \)-smooth integers were characterized by Störmer [14]. Building upon this work Lehmer [7] calculated the complete tables of consecutive \( p \)-smooth pairs for every prime \( p \leq 41 \).
Let \( G_p \) be the multiplicative subgroup of \( \mathbb{Q} \) generated by \(-1\) along with the \( p \)-smooth integers and define the \( p \)-smooth partial field as \( S_p = (\mathbb{Q}, G_p) \). As stated in Section 2, the fundamental elements are known for \( S_2 = \mathbb{D} \) and \( S_3 = \mathbb{GE} \). Theorem 3.1 gives the complete list of fundamental elements of \( S_5 \). Our proof of Theorem 3.1 relies on Propositions 3.2 and 3.3 and so extending both results to \( p \)-smooth integers for \( p \geq 7 \) would be required for determining the fundamental elements of \( S_p \). Indeed, Lehmer [7] accomplished the former task for all \( p \leq 41 \); however, extensions of Proposition 3.3 to three-term vanishing sums of \( p \)-smooth integers seems to be unexplored.
Consider \( M = 732,375 = 33 · 53 · 7 · 31 \) and reduce our equation to obtain \( 3b + 5c ≡ 2a \) mod \( M \). In \( \mathbb{Z}_M \), \( 3b ∈ \{3,9\} \) if and only if \( b ∈ \{1,2\} \) and \( 5c ∈ \{5,25\} \) if and only if \( c ∈ \{1,2\} \). Our assumption in this case is, of course, that \( b,c ≥ 3 \) so we let \( L_3 = \{3b mod M : 3 ≤ b ≤ M\} \), \( L_5 = \{5c mod M : 3 ≤ c ≤ M\} \), and \( L_2 = \{2a mod M : 0 ≤ a ≤ M\} \). We calculate these three sets in SageMath and then calculate that \( (L_3 + L_5) ∩ L_2 = ∅ \) as sets in \( \mathbb{Z}_M \) which implies that \( (a,b,c) \) is not a solution to \( 3b + 5c ≡ 2a mod M \), a contradiction.
The final calculation in Annex A of [13] is to check that the union of the sets of associates of the numbers listed contains \( 99 = 3 + 6(16) \) distinct numbers. Thus these 17 classes of associates are mutually disjoint.
If \( f \) is a fundamental element of \( \mathbb{S}_5 \), then either \( Assoc(f) \) contains an integer or does not contain an integer. In Case 1 we determine all integer fundamental elements of \( \mathbb{S}_5 \) and in Case 2 we determine the fundamental elements \( f \) for which \( Assoc(f) \) does not contain an integer.
Consider a non-negative integer \( a \). If \( a \) a non-trivial fundamental element of \( \mathbb{S}_5 \), then its associate \( 1 – a \) is a negative integer that is a fundamental element of \( \mathbb{S}_5 \). Thus \( (a – 1,a) \) is a pair of positive and consecutive 5-smooth integers. If \( -a \) is a non-trivial fundamental element of \( \mathbb{S}_5 \), then its associate \( 1 + a \) is a positive integer that is a fundamental element of \( \mathbb{S}_5 \). Again, \( (a,a + 1) \) is a pair of positive and consecutive 5-smooth integers. The only such pairs are given by Proposition 3.2. Thus the associates of \( 2,3,4,5,6,9,10,16,25,81 \) are all of the fundamental elements of \( \mathbb{S}_5 \) which are either integers or associates of integers.
Let \( \{p_1,p_2,p_3\} = \{2,3,5\} \) and \( ± p_1e1p_2e2p_3e3 \) be a fundamental element which is neither an integer nor the associate of an integer. We now have
Since \( p_1^{e_1}p_2^{e_2}p_3^{e_3} \) is not an integer, neither is its associate \( p_1^{f_1}p_2^{f_2}p_3^{f_3} \). Thus some \( e_i < 0 \) and some \( f_j < 0 \).
By way of contradiction, if each \( e_i \leq 0 \), then \( \pm p_1^{e_1}p_2^{e_2}p_3^{e_3} \) is the reciprocal of a 5-smooth integer which means that both \( \pm p_1^{e_1}p_2^{e_2}p_3^{e_3} \) and \( \pm p_1^{f_1}p_2^{f_2}p_3^{f_3} \) are associates of a 5-smooth integer. This is contrary to our assumption.
Suppose by way of contradiction that \( h_i = \min\{e_i, f_i\} > 0 \). We now have
in which \( a \) and \( b \) are rational numbers which when written in lowest terms do not have a factor of \( p_i \) in their denominator, a contradiction.
Suppose without loss of generality that \( e_1, f_2 > 0 \) which now implies that \( f_1, e_2 \leq 0 \). Again without loss of generality assume that \( e_3 \leq f_3 \) which implies that \( e_3 \leq 0 \). Eq. (1) now yields the integer equation;
in which \( p_1^{-f_1}p_2^{-e_2}p_3^{-e_3} \neq 1 \) (because otherwise, Eq. (1) becomes a difference of two \( p \)-smooth integers). Since a prime factor is shared by no more than two of the three terms in Eq. (2), each prime factor is
contained in at most one of the three terms. Hence Eq. (2) is actually one of \(2^a + 3^b = 5^c\), \(2^a + 5^c = 3^b\), and \(3^b + 5^c = 2^a\). The seven possible solutions to these equations are given in Proposition 3.3. Each of the seven solutions produces six equations of the form \(1 – a = b\) and so describes six fundamental elements of \(\mathbb{S}_5\) which form a complete class of six associates. These seven classes of associates are exactly the associates of the seven fractions listed in Theorem 3.1.
Let \(g\) be the golden ratio \(\frac{1+\sqrt{5}}{2}\); that is, the positive root of the polynomial \(x^2 – x – 1\). The golden-mean partial field is \(\mathbb{G} = (\mathbb{R}, \{\pm g^i : i \in \mathbb{Z}\})\). The non-trivial fundamental elements of \(\mathbb{G}\) are Assoc\((g) = \{g, -g, g^{-1}, -g^{-1}, g^2, g^{-2}\}\). For a prime \(p\), define the \(p\)-golden partial field \(\mathbb{G}_p = (\mathbb{R}, \{\pm g^i s : i \in \mathbb{Z} \text{ and } s \in \mathbb{S}_p\})\).
An interesting geometric property of \(\mathbb{G}_2\) is that \(\cos(\frac{n\pi}{5}) \in \{\pm 1, \pm \frac{g}{2}, \pm \frac{1}{2g}\} \subseteq \mathbb{G}_2\) for every \(n \in \mathbb{Z}\) and, furthermore, \(\cos(\frac{\pi}{5}) = \frac{g}{2}\) and \(\cos(\frac{3\pi}{5}) = \frac{-1}{2g}\) are both fundamental elements of \(\mathbb{G}_2\).
The there are 27 non-trivial fundamental elements of \(\mathbb{G}_2\). They partition into classes of associates of the following numbers.
In order to prove Theorem 4.1 we use the relationship between the golden ratio and the Fibonacci numbers. For \(n \geq 0\), define the \(n^{th}\) Fibonacci number \(f_n\) using \(f_0 = 0, f_1 = 1\), and \(f_n = f_{n-1} + f_{n-2}\) for \(n \geq 2\). Proposition 4.2 is well known and can easily be proven by induction.
For \(n \geq 0\), \(g^n = f_n g + f_{n-1}\) and \(g^{-n} = (-1)^n (-f_n g + f_{n+1})\).
fundamental element \(\pm 2^{i}g^{j}\) must have \(j\neq 0\). By Lemma 4.4, the set \(P=\{\pm 2^{i}g^{j}: -6\leq i\leq 3\) and \(|j|\in\{1,2,3,6\}\}\) contains the remaining fundamental elements of \({\mathbb{G}}_{2}\). From here we use the SageMath software package to check if \(1-a\in P\) for each \(a\in P\). The calculations are in Annex B of [13]. We also confirm that the classes of associates of the elements listed in our theorem are mutually disjoint and so contain 27 distinct elements in total.
Proof of Theorem 4.5. The rational fundamental elements of \( G_3 \) must be the fundamental elements of \( GE = S_3 \). These are the associates of 2,3,4,9. Any other fundamental element \( \pm 2^i 3^j g^k \) must have \( k \neq 0 \). By Lemma 4.6 the set \( P = \{\pm 2^i 3^j g^k : -16 \leq i \leq 8 \text{ and } -10 \leq j \leq 5 \text{ and } |k| \in \{1, 2, 3, 4, 6, 12\}\} \) contains all of the remaining fundamental elements of \( G_3 \). From here we use the SageMath software package to check if \( 1 – a \in P \) for each \( a \in P \). The calculations are in Annex C of [13]. We also confirm that the classes of associates of the elements listed in our theorem are mutually disjoint and so contain 81 distinct elements in total. \(\square\)
Theorem 4.7. The there are 195 non-trivial fundamental elements of \( G_5 \). They partition into classes of associates of the following numbers.
\[\frac{3}{128}, \frac{2}{27}, \frac{5}{32}, \frac{9}{25}, \frac{3}{8}, \frac{2}{5}, \frac{4}{9}, 2, 3, 4, 5, 6, 9, 10, 16, 25, 81,\]
\[\frac{5}{8}g, g, 2g^2, \frac{5}{2}g^2, \frac{8}{3}g^2, 3g^2, \frac{1}{3}g^3, g^3, 2g^4, 5g^4, 8g^4, \frac{1}{8}g^5, \frac{1}{3}g^5, 2g^5, g^6, 18g^6.\]
Lemma 4.8. If \(\pm 2^{i}3^{j}5^{k}g^{\ell}\) is a non-trivial fundamental element of \({\mathbb{G}}_{5}\) with \(\ell\neq 0\), then \(-17\leq i\leq 9\), \(-10\leq j\leq 5\), and \(-7\leq k\leq 4\), and \(|\ell|\in\{1,2,3,4,5,6,12\}\).
Proof. Fundamental element \(\pm 2^{i}3^{j}5^{k}g^{\ell}\) yields an equation
\[1\pm 2^{i}3^{j}5^{k}g^{\ell}=\pm 2^{a}3^{b}5^{c}g^{d},\] (5)
in which \(\pm 2^{a}3^{b}5^{c}g^{d}\) is also a fundamental element. Proposition 4.2 now implies that
\[2^{i}3^{j}5^{k}f_{|\ell|}g=2^{a}3^{b}5^{c}f_{|d|}g,\]
which yields
\[2^{i-a}3^{j-b}5^{k-c}f_{|\ell|}=f_{|d|}.\]
Using Theorem 4.3 and inspecting the values \(f_{0},\ldots,f_{12}\) we find that \(|\ell|,|d|\in\{1,2,3,4,5,6,12\}\), \(|a-i|\leq 4\), \(|b-j|\leq 2\), and \(|c-k|\leq 1\). Going back to (5) and again using Proposition 4.2 we get that \(1\pm 2^{i}3^{j}5^{k}f_{x}=\pm 2^{a}3^{b}5^{c}f_{y}\) where \(x\in\{|\ell|-1,|\ell|+1\}\) and \(y\in\{|d|-1,|d|+1\}\). Thus \(1=2^{i}3^{j}5^{k}|f_{x}\pm 2^{a-i}3^{b-j}5^{c-k}f_{y}|\). The expression \(|f_{x}\pm 2^{a-i}3^{b-j}5^{c-k}f_{y}|\) is nonzero and is at most \((f_{13}+720f_{13})=167,993\) and at least \(\frac{1}{720}\). This implies that \(-17\leq i\leq 9\), \(-10\leq j\leq 5\), and \(-7\leq k\leq 4\).
Proof of Theorem 4.7. The rational fundamental elements of \({\mathbb{G}}_{5}\) must be the fundamental elements of \({\mathbb{S}}_{5}\). These are listed in Theorem 3.1. Any other fundamental element \(\pm 2^{i}3^{j}5^{k}g^{\ell}\) must have \(\ell\neq 0\). By Lemma 4.6 the set \(P=\{\pm 2^{i}3^{j}5^{k}g^{\ell}:-17\leq i\leq 9\) and \(-10\leq j\leq 5\) and \(-7\leq k\leq 4\) and \(|\ell|\in\{1,2,3,4,5,6,12\}\}\) contains all of the remaining fundamental elements of \({\mathbb{G}}_{3}\). From here we use the SageMath software package to check if \(1-a\in P\) for each \(a\in P\). The calculations are in Annex D of [13]. We also confirm that the classes of associates of the elements listed in our theorem are mutually disjoint and so contain 195 distinct elements in total.