Keywords: Split graphs, factor graphs, 2-switches, degree sequences, induced triangles, differences of complementary divisors.

MSC 2020: 05C07, 05C75, 11A51.

1 Introduction↩︎

1.1 2-switches, realization graphs, and indecomposable split graphs↩︎

Let \(G\) be a graph. By \(V(G)\) and \(E(G)\) we denote, respectively, the set of vertices of \(G\) and the set of edges of \(G\). Given four distinct vertices \(a,b,x,y\) of \(G\) with \(ab, xy \in E(G)\) and \(ax, by \notin E(G)\), the process of replacing \(ab, xy\) with \(ax, by\) is said to be a 2-switch on \(G\). This local operation preserves the degree sequence of \(G\), and a classical theorem asserts that any two graphs with the same degree sequence are connected by a sequence of 2-switches (see [1]). The realization graph \(\mathcal{G}(d)\) of a degree sequence \(d\), whose vertices are the graphs with degree sequence \(d\) and whose edges correspond to 2-switches, is therefore connected; understanding its geometry has been an active line of research for several decades (see, e.g., [2], [3]).

A particularly natural invariant extracted from \(\mathcal{G}(d)\) is the 2-switch-degree \(\deg(G)\) of a graph \(G\), namely the degree of \(G\) as a vertex of \(\mathcal{G}(d)\). Equivalently, \(\deg(G)\) counts the number of distinct 2-switches acting on \(G\). This parameter, first studied systematically in [4], measures the local flexibility of \(G\) within its realization class and is closely related to several structural properties.

A graph is said to be split if its vertex set can be partitioned into a clique and an independent set (see [5]). Two results situate split graphs at the heart of the 2-switch-degree theory. On one hand, Tyshkevich proved in [6] that every graph \(G\) admits a unique decomposition \(G = G_r\circ \cdots \circ G_1\) into indecomposable factors, with the property that \(G_2, \ldots, G_r\) are all split graphs. On the other hand, Barrus and West introduced in [7] the auxiliary graph \(A_4(G)\), whose vertices are those of \(G\) and whose edges join pairs of vertices participating together in some 2-switch of \(G\), and showed that \(G\) is indecomposable in the sense of Tyshkevich if and only if \(A_4(G)\) is connected. Together with the fact that \(\deg(S\circ G)=\deg(S)+\deg(G)\) (see [4]), these two theorems reduce the problem of classifying all the split graphs with fixed degree to the problem of classifying all indecomposable split graphs with fixed degree.

1.2 The factor graph of a split graph↩︎

Motivated by this reduction, in [8] the authors introduced the factor graph \(\Phi(S)\) of a split graph \(S\). Let \((K,I)\) be a bipartition of \(V(S)\) into a clique \(K\) and an independent set \(I\). So, \(\Phi(S)\) is the loopless multigraph on \(I\) in which the multiplicity \(\sigma_{uv}\) of the edge \(uv\) records the number of 2-switches acting simultaneously on \(u\) and \(v\). Throughout this paper, the symbols \(d_v\) and \(N_v\) always denote, respectively, the degree and the neighborhood of a vertex \(v\) in the split graph \(S\). An explicit formula relates \(\sigma_{uv}\) to the neighborhoods of \(u\) and \(v\) in \(S\): \[\sigma_{uv} \;=\; \bigl(d_u - \eta_{uv}\bigr)\bigl(d_v - \eta_{uv}\bigr),\] where \(\eta_{uv} = |N_u \cap N_v|\). Summing multiplicities gives \(|E(\Phi(S))| = \deg(S)\), so the factor graph packages the 2-switch-degree of \(S\) together with its fine combinatorial structure. For this reason, \(\Phi(S)\) has emerged as the natural object to study the 2-switch dynamics of indecomposable split graphs (see [8], [9]).

The flow configuration of a split graph \((S,K,I)\), denoted by \(\vec{\Phi}(S)\), is defined as the digraph with \(I\) as vertex set, where there is an arc \((u,v)\) from \(u\) to \(v\) if and only if \(d_u\leq d_v\) in \(S\) and \(\sigma_{uv}>0\). Clearly, \(\vec{\Phi}(S)\) and \(\Phi(S)\) are isomorphic as simple graphs, ignoring multiple edges and arc directions. A key structural fact, established in [9], is that every induced cycle in \(\Phi(S)\) has length at most \(4\). It is easy to see that triangles of \(\vec{\Phi}\) fall into one of the four orientation types of 1. In this article we focus on the simplest and most symmetric case: triangles in which all three edges share a common multiplicity.

If \(H\) is a subgraph of \(\Phi\), we denote by \(\vec{H}\) the corresponding subgraph in \(\vec{\Phi}\). We say that \(H\) is \(n\)-simple if all the edges of \(H\) have multiplicity \(n\). A triangle \(T\) in \(\Phi\) is said to be of type 0 if \(\vec{T}=\Delta_0\) (up to labeling). The question driving this paper can now be stated cleanly.

1.3 The bridge to Number Theory: the \(\Delta\) property↩︎

At first glance, Problem 1 may appear overly specific. Its interest lies in an unexpected phenomenon: the set of natural numbers for which the answer to Problem 1 is affirmative admits a clean, purely arithmetic description. To state it, for \(n \in \mathbb{N}=\{1,2,3,\ldots\}\) let \(D_n\) denote the set of positive divisors of \(n\), and define \[D^*_n \;=\; \bigl\{\, |a - b| : a, b \in D_n,\;ab = n \,\bigr\}, \quad D^+_n \;=\; \bigl\{\, x + y : x, y \in D^*_n - \{0\} \,\bigr\}.\] That is, \(D^*_n\) collects the differences between complementary divisors of \(n\), and \(D^+_n\) the pairwise sums of the nonzero such differences. We say that \(n\) has the \(\Delta\) property (or satisfies the \(\Delta\) condition) when \[D^*_n \cap D^+_n \;\neq\; \varnothing,\] and we denote by \(\mathbb{N}(\Delta)\) the set of all natural numbers with the \(\Delta\) property. By inspection, the two smallest members of \(\mathbb{N}(\Delta)\) are \(24\) and \(40\), because \[\tfrac{24}{2} - 2 \;=\; 10 \;=\; 2\left(\tfrac{24}{3} - 3\right), \qquad \tfrac{40}{4} - 4 \;=\; 6 \;=\; 2\left(\tfrac{40}{5} - 5\right).\] This article is divided into 5 sections. The first part of 2 is devoted to basic facts about the \(\Delta\) condition, encoding them through the notion of a \(\Delta\)-triple \((x,y,z)\) of divisors of \(n\). We bound the components of any such triple, and determine the optimal upper bound on \(n\) in terms of its smallest component \(x\), separately in the regimes \(y=z\) and \(y<z\) ([prop:max-duplicated,prop:max-generic]). One of the main results of this work then links Problem 1 to the \(\Delta\) condition in the second (last) part of 2:

The forward implication in 2 solves an explicit realization problem starting from a number-theoretic datum, while the reverse implication extracts an arithmetic invariant from a purely combinatorial configuration. Together they provide a two-way bridge between Graph Theory and Number Theory.

1.4 The set \(\mathbb{N}(\Delta)\) as a number-theoretic object↩︎

2 motivates the systematic study of \(\mathbb{N}(\Delta)\) as a number-theoretic object, which occupies the remainder of the article, i.e., from 3 and beyond.

In 3 we observe that \(\alpha^{2} n \in \mathbb{N}(\Delta)\) whenever \(n \in \mathbb{N}(\Delta)\) and \(\alpha \in \mathbb{N}\), which immediately yields \(|\mathbb{N}(\Delta)| = \infty\) and motivates the notion of a \(\Delta\)-primitive number: an element of \(\mathbb{N}(\Delta)\) that is not a nontrivial square multiple of any smaller element of \(\mathbb{N}(\Delta)\). \(\Delta\)-primitives play the role of multiplicative atoms for \(\mathbb{N}(\Delta)\), in loose analogy with primes for \(\mathbb{N}\): every member of \(\mathbb{N}(\Delta)\) decomposes as the square of an integer times a \(\Delta\)-primitive, and every square-free element of \(\mathbb{N}(\Delta)\) is itself \(\Delta\)-primitive. We further show that the subset \(\mathbb{N}(\Delta^{2}) \subset \mathbb{N}(\Delta)\) of squares with the \(\Delta\) property is closed under multiplication; it therefore forms an abelian semigroup under the ordinary product. We then study the uniqueness of the decomposition \(n = \alpha^{2} m\) into a square and a \(\Delta\)-primitive: we prove that it is unique whenever two such decompositions have coprime \(\Delta\)-primitive parts (10), but that uniqueness fails in general. This leads to a refined uniqueness conjecture, phrased in terms of the \(\Delta\)-primitives sharing a given square-free part. Finally, we close the section by constructing a cubic polynomial generator of numbers with the \(\Delta\) property, through which we prove that there are infinitely many \(\Delta\)-primitives (9).

In 4 we develop a systematic way to produce elements of \(\mathbb{N}(\Delta)\) through generating polynomials. The starting point is that \[x(2x-1)(3x-2) \in \mathbb{N}(\Delta) \qquad \text{for every integer } x \geq 2,\] which is used to prove the infinitude of \(\Delta\)-primitive numbers in 3.3. We then generalize the construction and exhibit an infinite family of cubic polynomials \(n(x)\) whose values lie in \(\mathbb{N}(\Delta)\) for all sufficiently large integers \(x\) (11). Two complementary results delimit the reach of this method: it produces no generating polynomial of degree \(\geq 4\) (12) and no linear family realizing the regime \(y < z\) in degree \(3\) (13).

Whether \(\mathbb{N}(\Delta^{2})\) contains infinitely many \(\Delta\)-primitive squares remains an open problem (Conjecture 10). However, we note a suggestive connection: for each cubic generating polynomial \(f\) produced by our method, locating squares in \(f(\mathbb{N}) \cap \mathbb{N}(\Delta)\) amounts to finding integer points on the elliptic curve \(y^{2} = f(x)\). By Siegel’s theorem (see [10]), each such curve contributes only finitely many integer points; however, the infinite family of generating polynomials given by 11 raises the possibility of constructing a family of elliptic curves that collectively yields infinitely many \(\Delta\)-primitive squares. We develop this perspective in 4.4.

The complementary part of the theory concerns integers that fail the \(\Delta\) condition. This is the content of 5. Two guiding heuristics emerge from our analysis. The first is that a prime appearing in the factorization of \(n\) which is “large” compared to \(n\) obstructs the \(\Delta\) property: concretely, \(pk \notin \mathbb{N}(\Delta)\) whenever \(p \geq k\), and an analogous phenomenon occurs for numbers of the form \(p^{x}q^{y}\) when \(q > p^{x}\), where \(p,q\) are primes ([p>2k-2_entonces.pk.no tiene.prop.Delta,p^xq^y.no.tiene.prop.Delta.q>p^x]). The second heuristic is that integers with few distinct prime factors tend to fall outside \(\mathbb{N}(\Delta)\): this is true for all prime powers, as well as for several families of integers with exactly two prime divisors. Sharper than these heuristics is a complete characterization of which products of three distinct primes lie in \(\mathbb{N}(\Delta)\) (22). As a consequence, the obstructions of 5 restrict the possible values of the divisor-counting function \(\tau\) on \(\mathbb{N}(\Delta)\) (12).

1.5 Returning to graphs↩︎

Obstructions to the \(\Delta\) condition translate back into obstructions at the level of the factor graph. As a sample of this translation, we close 5 with the following structural consequence: if \(n \in \mathbb{N}\) is neither a perfect square nor an element of \(\mathbb{N}(\Delta)\), then every \(n\)-simple induced cycle of \(\Phi(S)\) has length \(4\) (23).

2 \(\Delta\) property and \(n\)-simple triangles in \(\Phi(S)\)↩︎

2.1 Basic facts about \(\Delta\)-triples↩︎

A triple \((x,y,z)\) of divisors of \(n\) satisfying all the requirements of 2 is called a \(\Delta\)-triple for \(n\). Through elementary algebraic manipulations, ?? can be rewritten as \[(xy+xz-yz)n=xyz(z+y-x). \label{ecuacion246Delta46prop}\tag{1}\]

2.2 Optimal bounds on \(n\) in terms of \(x\)↩︎

The bounds on \(y\) and \(z\) established in [prop:y/x.cota.universal,prop:bound-z] constrain the components of any \(\Delta\)-triple, but do not by themselves bound \(n\). In this subsection we determine the optimal upper bound on \(n\) in terms of \(x\), separately for each of the two regimes \(y=z\) and \(y<z\). Both bounds rest on a single change of variables: setting \(u = y-x\) and \(v = z-x\), the equality 1 characterizing a \(\Delta\)-triple becomes \[\label{eq95delta95u61y-x9595v61z-x} n \;=\; n(x,u,v) \;=\; \frac{x(x+u)(x+v)(x+u+v)}{x^{2}-uv},\tag{2}\] and the admissibility condition \(xy+xz-yz \ge 1\) reduces to \(uv \le x^{2}-1\). By [prop:y/x.cota.universal,prop:bound-z], the integers \(u,v\) satisfy \(1 \le u \le v \le x^{2}-1\). The two regimes \(y=z\) and \(y<z\) correspond to \(u=v\) and \(u<v\), respectively. In each, the maximization of \(n\) reduces to elementary monotonicity arguments.

If $y \ge x+2$, then $z \ge y+1 \ge x+3$, so
$(y-x-1)(z-x-1)\ge 1\cdot 2>0$, which expands to $u+v < p + 1$.
Hence, $(x+u)(x+v)<(x+1)(x+p)$ and $x+u+v<x+p+1$. Therefore,
$n < f(p) \le f(x^{2}-1)=F(x)$.

If $y = x+1$ and $z \le x^{2}+x-2$, then $p = z-x \le x^{2}-2$, so
by the strict monotonicity of $f$: $n\le f(p)<f(x^2-1)=F(x)$.

Observe from 4(3) that the family of \(\Delta\)-triples \(\{(x, x+1, x^2 + x - 1):x\ge 2\}\) saturates the bound \(z<x(x+1)\) of 4.

2.3 Arithmetic constraint when \(y=z\)↩︎

The optimal bounds of 2.2 measure how large \(n\) can be; they say nothing about how its prime structure is organized. We close the section by recording the arithmetic counterpart for the duplicated regime \(y = z\). Writing \(x=ad\) and \(y=bd\), where \(d = \gcd(x, y)\) and \(\gcd(a,b)=1\), shows that 1 becomes a descent identity that ties \(n\) to the square factor \(d^2\). Moreover, we obtain a sharp divisibility constraint: \(\gcd(2a-b,ab(2b-a))|6\).

2.4 From Graphs to Numbers↩︎

As announced in 1, the following theorem, is very important because it provides a bridge from Graph Theory to Number Theory. Its proof is surprisingly simple.

2.5 From Numbers to Graphs↩︎

A split graph \((S,K,I)\) is said to be balanced if \(|K|=\omega(S)\) and \(|I|=\alpha(S)\), where \(\omega(S)\) is the clique number of \(S\) and \(\alpha(S)\) is the independence number of \(S\) (see [5]). Otherwise, we say that \(S\) is unbalanced. \(S\) is unbalanced if and only if \((|K|,|I|)\in\{(\omega(S),\alpha(S)-1), (\omega(S)-1,\alpha(S))\}\) ([5], Theorem 7). To prove the following lemma, we use some notations, concepts and results about unbalanced split graphs from Section 4 of [11] (in particular, about swing vertices).

A vertex \(v\) of a graph \(G\) is said to be active if \(v\) is involved in some 2-switch on \(G\) (see [4]). Otherwise, \(v\) is inactive. We say that \(G\) is active if all of its vertices are active. We say that \(G\) is decomposable (with respect to the Tyshkevich composition \(\circ\), see [6]) if \(G=S\circ H\) for some split graph \(S\) and graph \(H\), both with at least one vertex. Otherwise, \(G\) is indecomposable. Every nontrivial indecomposable graph is active. \(G=S\circ H\) is active if and only if \(S\) and \(H\) are active. An active split graph is indecomposable if and only if \(\Phi(S)\) is connected (see [8]).

If 6 can be thought of as a bridge from Graphs to Numbers, the following result goes in the opposite direction, that is, from Number Theory back to Graph Theory. For this reason, we consider it another key theorem of this section.

Let us apply 7 to the \(\Delta\)-triple \((2,3,3)\) for \(n=24\), taking \(d_a=3\). We obtain an indecomposable split graph \(S\) with \(|K|=18\), \(d_b=8\), \(d_c=13\), \(\eta_{ab}=0\), \(\eta_{bc}=5\) and \(\eta_{ac}=1\). The following neighborhoods are compatible with these parameters: if \(K=[18]\), define \(N_a=[3], N_b=\{4,\ldots,11\}\), and \(N_c=\{3,\ldots,8,12,\ldots,18\}\). Thus, \(N_a\cap N_b=\varnothing, N_b\cap N_c=\{4,\ldots,8\}\), and \(N_a\cap N_c=\{3\}\). It can be easily checked that \(\Phi(S)\) is a \(24\)-simple triangle by direct computation of the \(\sigma_{uv}\)’s. In 3, we show a simplified version of the split graph \(S\) we have just constructed, omitting all edges between clique vertices (in black).

3 \(\Delta\)-primitive numbers↩︎

Thanks to 7, we see that \(|\mathbb{N}(\Delta)|=\infty\). Another immediate consequence of this proposition is that if \(n\in\mathbb{N}(\Delta)\) and \(n^{2\beta}\in\mathbb{N}(\Delta)\) for some \(\beta\in\mathbb{N}\), then \(\{n^k:k\in[2\beta,\infty)\cap\mathbb{N}\}\subset\mathbb{N}(\Delta)\). For example, both \(84\) and \(84^2\) have the \(\Delta\) property, so all higher powers of 84 do as well.

7 allows us to trivially obtain infinitely many elements of \(\mathbb{N}(\Delta)\) from others. This motivates the search and study of those numbers with the \(\Delta\) property that cannot be obtained in this way. We say that a natural number \(n\) is \(\Delta\)-primitive if \(n\in\mathbb{N}(\Delta)\) and there is no pair of numbers \(\alpha,m\geq 2\) such that \(n=\alpha^2m\) and \(m\in\mathbb{N}(\Delta)\). For example, 24 and 40 are \(\Delta\)-primitive numbers. On the other hand, 96 is not, since we can write it as \(2^2 \cdot 24\).

Clearly, if \(n\in\mathbb{N}(\Delta)\) and \(n\) is square-free, then \(n\) is \(\Delta\)-primitive. Examples of square-free numbers satisfying the \(\Delta\) condition are 105 and 385. Therefore, 105 and 385 are \(\Delta\)-primitive. Moreover, 105 is the smallest odd number with the \(\Delta\) property.

The notion of \(\Delta\)-primitivity, together with the decomposition of 8, raises three natural questions:

1. Is the decomposition of 8 unique?

2. Are there infinitely many \(\Delta\)-primitive numbers?

3. Are there infinitely many \(\Delta\)-primitive squares?

In the remainder of this section we address (1) (10) and (2) (9), while (3) remains open (Conjecture 10).

3.1 Squares with the \(\Delta\) property↩︎

An interesting consequence of 7 is that the set \(\mathbb{N}(\Delta^2)\) of all squares satisfying the \(\Delta\) condition is closed under multiplication.

With the help of a computer, one can verify that \(30^{2}\) is the first element of \(\mathbb{N}(\Delta^{2})\). Then \(|\mathbb{N}(\Delta^{2})| = \infty\), by 7.

The answer to (1) turns out to depend on whether \(n\) is a perfect square or not. In the square case, uniqueness genuinely fails: given any two distinct \(\Delta\)-primitive squares, we can construct an \(n\) admitting more than one decomposition of the form \(n = \alpha^{2} m\) with \(m\) \(\Delta\)-primitive.

We illustrate this with an example. With the help of a computer, one can determine that \(84^{2}\) is the next smallest \(\Delta\)-primitive square after \(30^{2}\). By 7, \(30^{2} a^{2}, 84^{2} b^{2} \in \mathbb{N}(\Delta)\) for all \(a, b \in \mathbb{N}\). Therefore, if we find a pair \((a, b) \in \mathbb{N}^{2}\) satisfying \[\label{eq27} 30^{2} a^{2} = 84^{2} b^{2},\tag{5}\] then \(n = 30^{2} a^{2}\) is the number we are looking for. Obviously, 5 has the same solutions as \(5a = 14b\) in \(\mathbb{N}^{2}\). Since \(5\) and \(14\) are coprime, we obtain \(a = 14 a_{1}\), \(b = 5 b_{1}\) for some \(a_{1}, b_{1} \in \mathbb{N}\), and substituting back yields \(a_{1} = b_{1}\). Therefore, the solutions are of the form \((a, b) = (14k, 5k)\) for \(k \in \mathbb{N}\), and \(n = 420^{2} k^{2}\). The following proposition generalizes this procedure.

3.2 Uniqueness of decompositions in \(\mathbb{N}(\Delta)\)↩︎

9 shows that uniqueness of decomposition in \(\mathbb{N}(\Delta)\) is essentially a non-square phenomenon. To make this idea precise, we now establish a partial uniqueness result in the non-square case, under the additional assumption that the two \(\Delta\)-primitive parts of the decompositions are coprime. The following three lemmas provide partial information towards the uniqueness of the decomposition of 8.

Let \(p\) be a prime number and let \(n\in\mathbb{N}\) with \(n\neq 0\). The \(p\)-adic valuation of \(n\), denoted by \(v_p(n)\), is the largest integer \(k\geq 0\) such that \(p^k \mid n\). We recall the following basic property of \(v_p\): for all \(a,b\in\mathbb{N}\), \[v_p(ab) = v_p(a) + v_p(b),\] and \(n\) is a perfect square if and only if \(v_p(n)\) is even for every prime \(p\).

The content of 10 can be paraphrased as follows: in the non-square case, no number \(n\) admits two decompositions \(n = a^{2} x = b^{2} y\) with \(x, y\) coprime \(\Delta\)-primitives. 10 might suggest the conjecture that every non-square \(n \in \mathbb{N}(\Delta)\) admits a unique decomposition \(n = \alpha^{2} m\) with \(\alpha \in \mathbb{N}\) and \(m\) \(\Delta\)-primitive. This is false. The smallest counterexample is \[n \;=\; 5616 \;=\; 2^{4} \cdot 3^{3} \cdot 13 \;=\; 3^{2} \cdot 624 \;=\; 2^{2} \cdot 1404,\] where \(624 = 2^{4} \cdot 3 \cdot 13\) is realized in \(\mathbb{N}(\Delta)\) by the \(\Delta\)-triple \((8, 13, 13)\), and \(1404 = 2^{2} \cdot 3^{3} \cdot 13\) by \((26, 27, 36)\); both 624 and 1404 are \(\Delta\)-primitive. Note that they share the same square-free part, \(3 \cdot 13 = 39\), and that \(\gcd(624, 1404) = 156 > 1\), so the coprimality hypothesis of 10 is violated. The problem of classifying the non-square integers \(n\) admitting multiple \(\Delta\)-primitive decompositions appears to be a delicate open problem.

The counterexample \(5616\) points to a natural refinement of the uniqueness question. For each square-free \(s \in \mathbb{N}\), let \(P(s)\) denote the set of \(\Delta\)-primitives with square-free part \(s\). A non-square \(n \in \mathbb{N}(\Delta)\) with square-free part \(s\) admits multiple \(\Delta\)-primitive decompositions only if \(|P(s)| \geq 2\). We conjecture that the converse also holds:

3.3 Infinitude of \(\Delta\)-primitive numbers↩︎

4 Generating polynomials↩︎

In this section, we revisit and expand upon an idea that arose in [prop:max-duplicated,prop:max-generic], developing a method for creating generating polynomials for numbers with the \(\Delta\) property.
If \(x\) is a natural number \(>1\), consider \[\label{eq34} n=n(x)=x(x+2)(2x+1).\tag{7}\] Now observe that \[x(2x+1)-(x+2) = 2(x(x+2)-(2x+1)),\] which is equivalent to \[\label{eq29} \frac{n}{x+2}-(x+2)=2\Big( \frac{n}{2x+1}-(2x+1) \Big).\tag{8}\] Since for all \(x>1\) we have that \(x+2, 2x+1\in D_n\) and \[1<x+2<2x+1<\sqrt{n},\] it follows from 8 that \(n\in\mathbb{N}(\Delta)\) for all \(x>1\), since all requirements of 2 are satisfied. These simple calculations, together with what we saw in [prop:max-duplicated,prop:max-generic], suggest the possibility of finding a more general method for constructing generating polynomials for numbers with the \(\Delta\) property.

4.1 The duplicated method “\(y=z\)”↩︎

Consider polynomials of the form \[n(x)=\prod_{i=1}^{k}(a_ix+b_i),\] with \(a_i,b_i\in\mathbb{Z}\), such that each linear factor \(a_ix+b_i\) of \(n\) is an element of \(D_n\). Clearly, we must have \(k\geq 2\), since we always need \(n\) to have at least two nontrivial divisors for sufficiently large \(x\).

If \(k=2\), then suppose that \(n=(a_1x+b_1)(a_2x+b_2)\) satisfies the \(\Delta\) property via its divisors \(a_1x+b_1\) and \(a_2x+b_2\). Without loss of generality, this can only happen in the following way: \[\label{eq30} \frac{n}{a_1x+b_1}-(a_2x+b_2)=2\Big( \frac{n}{a_2x+b_2}-(a_1x+b_1) \Big).\tag{9}\] Simplifying expression 9 , we obtain \[\label{eq31} (a_2-a_1)x+(b_2-b_1)=0.\tag{10}\] The key to the method we wish to present is this: if the left-hand side of 10 is the identically zero polynomial, then 9 holds. Therefore, we take \(a_2-a_1=0=b_2-b_1\), that is, \(a_2=a_1\) and \(b_2=b_1\). However, now \(n=(a_1x+b_1)^2\), so \(a_1x+b_1=\sqrt{n}\), which is not acceptable by 2. Hence, we must have \(k\geq 3\).

For each \(k\geq 3\), we now define the following polynomial: \[\label{eq32} f(x) = \frac{n}{a_1x + b_1} - (a_1x + b_1) - 2\left(\frac{n}{a_2x + b_2} - (a_2x + b_2)\right).\tag{11}\] Let \(k=3\). Observe that the conditions \(0<a_1<a_2\) and \(a_3>0\) are sufficient to guarantee the existence of some \(n_0\in\mathbb{N}\) such that the inequalities \[1<a_1x+b_1<a_2x+b_2<\sqrt{n(x)}\] hold simultaneously for \(x\in[n_0,\infty)\). Moreover, since all \(a_i\) are positive, we also ensure that \(\deg(n)=3\) and that \(n\) is eventually increasing. Through basic manipulations, we rewrite 11 as \(f(x)=c_2x^2+c_1x+c_0\), where \[c_2= a_2a_3 - 2a_1a_3,\] \[c_1= a_2b_3 + a_3b_2 - a_1 - 2a_1b_3 - 2a_3b_1 + 2a_2,\] \[c_0= b_2b_3 - b_1 - 2b_1b_3 + 2b_2.\] Since \(f=0\) implies \(n\in\mathbb{N}(\Delta)\) for all \(x\geq n_0\), we must find integer solutions of the system \(c_2=c_1=c_0=0\) in the six unknowns \(a_i,b_i\). From \(c_2=0\) we deduce that \(a_2=2a_1\), which is compatible with assuming \(a_1<a_2\). Substituting \(a_2=2a_1\) into \(c_1=0\) and \(c_0=0\), we obtain respectively that \((2b_1-b_2)a_3=3a_1\) and \((2b_1-b_2)b_3=2b_2-b_1\). Since \(a_1,a_3\neq 0\), it follows that \(2b_1-b_2\neq 0\), which allows us to isolate: \[a_3=\frac{3a_1}{2b_1-b_2}, \quad b_3=\frac{2b_2-b_1}{2b_1-b_2}.\] We note that \(a_1,a_3>0\) implies \(2b_1>b_2\); in particular, \((b_1,b_2)\neq(0,0)\) and \(b_3\geq 0\) if and only if \(2b_2\geq b_1\). We see that \(a_1,b_1\), and \(b_2\) end up being free parameters. Finally, for \(a_3,b_3\in\mathbb{Z}\), it is sufficient that \(2b_1-b_2\) divides \(\gcd(3a_1,2b_2-b_1)\). We summarize all this in the following theorem.

Let us see some examples of how to use 11 to construct generating polynomials for numbers with the \(\Delta\) property.

If \(\gcd(3a,2c-b)\) is a prime \(p\), then \(2b-c\in\{1,p\}\). If \(2b-c=1\), then \(c=2b-1\), \(\alpha=3a\), and \(\beta=3b-2\), yielding \[n(x)=(ax+b)(2ax+2b-1)(3ax+3b-2),\] for \(a\in\mathbb{N}\) and \(b\in\mathbb{Z}\). For example, if \((a,b)=(3,4)\), then \[(3x+4)(6x+7)(9x+10)\in\mathbb{N}(\Delta),\] for all \(x\in\mathbb{N}\). If instead \((a,b)=(1,0)\), we recover the polynomial \(x(2x-1)(3x-2)\) from 3.

If \(2b-c=p\), then \(c=2b-p\), \(\alpha=\frac{3a}{p}\), and \(\beta=\frac{3b}{p}-2\). Then: either \(p=3\), or \(p\neq 3\) and \(p\mid\gcd(a,b)\). If \(p=3\), then \(c=2b-3\), \(\alpha=a\), and \(\beta=b-2\), so \[n(x)=(ax+b)(2ax+2b-3)(ax+b-2).\] For example, if \((a,b)=(1,-1)\), then \[(x-1)(2x-5)(x-3)\in\mathbb{N}(\Delta),\] for all \(x\geq 5\), \(x\in\mathbb{N}\). If instead \((a,b)=(1,2)\), we recover the polynomial 7 . If \(p\neq 3\) and \((a,b)=(2,-4)\), then \(p=2\), \(c=-10\), \(\alpha=3\), and \(\beta=-8\). Hence, \[4(x-2)(2x-5)(3x-8)\in\mathbb{N}(\Delta),\] for all \(x\geq 4\), \(x\in\mathbb{N}\).

4.2 The failure of the duplicated method for \(k \geq 4\)↩︎

The method developed above relies crucially on the duplicated regime \(y = z\) of the \(\Delta\) condition: two of the three divisors in a \(\Delta\)-triple are forced to coincide. At the level of the generating polynomial, this manifests itself in the factor \(2\) appearing in 11 , which couples two linear factors of \(n(x)\) as \(x\) and \(y = z\). One may ask whether the same duplicated method can be extended to products of \(k \geq 4\) linear factors in order to produce generating polynomials of higher degree. The purpose of this subsection is to show that the answer is negative: the duplicated method breaks down for every \(k \geq 4\), by an obstruction concentrated on the leading coefficients of the resulting polynomial.

Concretely, fix \(k \geq 3\) and consider a product \[n(x) \;=\; \prod_{i=1}^{k}(a_{i} x + b_{i}), \qquad a_{i} \in \mathbb{N},\;b_{i} \in \mathbb{Z},\] in which \(X = a_{1} x + b_{1}\) and \(Y = a_{2} x + b_{2}\) are chosen to play the role of \(x\) and \(y = z\) in the \(\Delta\) condition. Write \(M\) for the product of the remaining \(k-2\) linear factors, so that \(n/X = Y M\) and \(n/Y = X M\). The duplicated \(\Delta\) condition \(\tfrac{n}{X} - X = 2\!\left(\tfrac{n}{Y} - Y\right)\) becomes the polynomial identity \(f= 0\), where \[\label{eq:duplicated-fk} f \;=\; (Y - 2X)M \;+\; (2Y - X).\tag{12}\]

12 should not be read as an obstruction to generating polynomials of degree \(\geq 4\), but rather as an indication that a different ansatz is required. Indeed, for \(k \geq 4\) the natural replacement is the generic regime \(y < z\): three distinct linear factors \(X, Y, Z\) of \(n(x)\) play the roles of the three divisors in a \(\Delta\)-triple for \(n\) and the \(k-3\) remaining factors form the free mass of the construction. The resulting polynomial identity reduces to a system of equations whose systematic treatment we leave to future work.

4.3 The failure of the generic method for \(k = 3\)↩︎

The previous subsection rules out the duplicated ansatz \(y = z\) for \(k \geq 4\). We now establish the complementary obstruction: in the generic regime \(y < z\), no linear \(\Delta\)-family exists for \(k = 3\). The proof reduces 1 to a polynomial identity governed by the polynomial \(x^{2} - x + 1\), whose irreducibility over \(\mathbb{R}\) provides the obstruction. The starting point is the following result, characterizing the case \(n = xyz\).

The smallest examples where 11 applies are 385 and 2080, with \(\Delta\)-triples \((5,7,11)\) and \((8,10,26)\), respectively.

4.4 Elliptic curves and \(\Delta\)-primitive squares↩︎

The generating polynomials of 11 produce elements of \(\mathbb{N}(\Delta)\) in abundance, but they say nothing about which of those elements are squares. This is precisely the question left open by Conjecture 10, and it admits a natural reformulation in terms of integer points on elliptic curves.

Let \(f\in\mathbb{Z}[x]\) be any of the cubic generating polynomials supplied by 11. Then \(f(x_0)\) is a perfect square (hence, a square in \(\mathbb{N}(\Delta)\)) precisely when \((x_0,y_0)\) is an integer point on the affine cubic \(E_f: y^2=f(x)\). By Siegel’s theorem [10], each individual curve \(E_f\) carries only finitely many integer points. However, 11 provides an infinite family \(\{f_\lambda\}\) of cubic generating polynomials, and therefore an infinite family \(\{E_{f_\lambda}\}\) of elliptic curves. This suggests a concrete strategy toward Conjecture 10.

A positive answer to Problem 14 would settle Conjecture 10 affirmatively and would constitute, to our knowledge, the first application of diophantine geometry to 2-switch-degree theory.

5 Numbers without the \(\Delta\) property↩︎

In this section we present a long list of families of numbers that do not satisfy the \(\Delta\) condition. This class of numbers is infinite. We note that numbers with very few prime factors in their factorization are less likely to have the \(\Delta\) property. Moreover, having information about the ordering of the elements of \(D_n\) is crucial to prove that \(n \notin \mathbb{N}(\Delta)\). After all this analysis, we return to split graphs, establishing a result about the \(n\)-simple induced cycles of \(\Phi\), when \(n\) does not satisfy the \(\Delta\) condition and is not a square.

15 has two direct consequences worth highlighting. The first is that \(|\mathbb{N} - \mathbb{N}(\Delta)| = \infty\). The second is that \(\mathbb{N}(\Delta)\) contains no even square-free numbers. In other words, every even number in \(\mathbb{N}(\Delta)\) is a multiple of 4.

5.1 The dominating-prime obstruction↩︎

The next result is of notable importance because it tells us that a number cannot satisfy the \(\Delta\) condition if it is divisible by a “sufficiently large" prime.

16 is useful for generating numbers without the \(\Delta\) property, since for each \(k \in \mathbb{N}\), we have infinitely many choices for \(p\). It is interesting to note what the contrapositive of this proposition tells us: if \(pk \in \mathbb{N}(\Delta)\), then \(p < k\). In other words, there are only finitely many prime multiples of a number that satisfy the \(\Delta\) property. Another important observation is that 16 implicitly provides a recipe to construct, for each prime \(k_1\), an infinite sequence \(\ell(k_1)=(k_i)_{i\in\mathbb{N}}\) of square-free numbers that do not have the \(\Delta\) property: set \(k_{i+1}=p_i k_i\), where \(p_i\) is any prime \(\geq k_i\) coprime to \(k_i\). For instance, starting from \(k_1=2\) with successive choices \(p_i=3,7,43,\ldots\), we obtain \(\ell(2)=(2,6,42,1806,\ldots)\).

The next result we prove, closely resembles 16 in style. It states that a number cannot have the \(\Delta\) property if its factorization contains exactly two primes and one of them is “much larger" than the other.

As an application of 8, consider a number \(n\) of the form \(9q^y\), with \(y \geq 2\). If \(n \in \mathbb{N}(\Delta)\), then it must be that \(q < 9\), i.e., \(q \in \{2, 5, 7\}\).

5.2 Integers of the form \(p^k\), \(pq\), \(pq^2\) and \(p^2q^2\)↩︎

5.3 Integers of the form \(p^kq\)↩︎

Having ruled the products of two primes with exponents \(\le 2\), we now turn to the family \(p^kq\) (\(p,q\) primes, \(k\in\mathbb{N}\)), where allowing \(k\) to grow yields not an obstruction but a complete classification. We start with a technical lemma we need later to prove that 24 and 40 are the only \(\Delta\)-primitives of the form \(p^k q\).

Based on experimental evidence, we conjecture that 24 and 40 are the only \(\Delta\)-primitive numbers using exactly two primes in their decomposition.

5.4 Products of three distinct primes↩︎

9 cannot be extended to a product \(p q r\) of three distinct primes: numbers like \(105 = 3 \cdot 5 \cdot 7\) and \(385 = 5 \cdot 7 \cdot 11\) would be counterexamples. However, we will analyze this new situation to understand in detail how the case \(p q\) differs from the case \(p q r\).

Let \(p, q\), and \(r\) be primes such that \(p < q < r\). If \(n = p q r\), then \[D_n^* = \{n - 1, q r - p, p r - q, |p q - r|\},\] \[D_n^+ = \{q r - p + p r - q, q r - p + |p q - r|, p r - q + |p q - r|\} \cup\] \[\cup (D_n^* + (n - 1)) \cup 2 D_n^*,\] where the elements of \(D_n^*\) are listed in decreasing order. This complete ordering is due to \(1 < p < q < r, \;p q < p r < q r < n\). To determine whether \(D_n^*\) and \(D_n^+\) are disjoint, we examine all possible equalities \(a + b = c\) with \(a, b, c \in D_n^* - \{0\}\). Since \(a + b > a,b\) (both summands being positive), neither summand can coincide with the sum. Moreover, by 1, \(n - 1\) cannot belong to \(D_n^* \cap D_n^+\). After these reductions, only the following cases remain:

The impossibility of (1), (2), (4), and (6) is evident due to the complete ordering of the elements of \(D_n^*\).

If \(r < p q\), then (7) can be rewritten as \(p (2q + 1) = r (q + 2)\), so \(q = k p - 2\), for some \(k \in \mathbb{N}\). Then, \(k (2p - r) = 3\), and thus \(k \in \{1, 3\}\). If \(k = 1\), then \(q = p - 2 < p\). If \(k = 3\), then \(r = 2p - 1 < 3p - 2 = q\). Both cases contradict the hypotheses. If \(p q < r\), then (7) is equivalent to \(r (2 - q) = p (2q - 1)\), which is obviously false.

If \(r < p q\), equality (8) can be rewritten as \(q (2p + 1) = r (p + 2)\). Since \(q (2p + 1)\) is odd, necessarily \(p \neq 2\). Moreover, \(q | (p + 2)\), which implies \(q \leq p + 2\). But then \(q = p + 2\), since \(3 \leq p < p + 2 \leq q\), and thus \(r = 2p + 1\). If \(p q < r\), then we can convert (8) into \(r (2 - p) = q (2p - 1)\), which is clearly absurd.

We can rewrite (5) as \(p (2r + 1) = q (r + 2)\). Then, \(2r + 1 = k q\) and \(r + 2 = h p\), for certain \(k, h \in \mathbb{N}\). But then \(p k q = q h p\), i.e., \(k = h\), from which we deduce that \(k (2p - q) = 3\). Hence, \(k \in \{1, 3\}\). If \(k = 1\), then \(r = p - 2 < p\), a contradiction. If \(k = 3\), then \(r = 3p - 2\) and \(q = 2p - 1\).

Regarding equality (3), note that it can be rewritten as \[(r + p + 1)(q - p - 1) = -p^2 - p - 1,\] if \(p q < r\), and \[(r - p + 1)(q - p + 1) = p^2 - p + 1,\] if \(r < p q\). The first case is immediately discarded. Regarding the second, we can say that \(d_1 = q - p + 1\) and \(d_2 = r - p + 1\) are complementary divisors of the integer \(m = d_1 d_2 = p^2 - p + 1\). Therefore, by fixing \(p\), we will have a finite number of pairs \((q, r)\) such that \(p q r \in \mathbb{N}(\Delta)\). We also note that: 1) \(1 < d_1 < \sqrt{m}\); 2) \(m, d_1\) and \(d_2\) are odd for \(p > 2\). We can summarize all this analysis in the following proposition.

Notice that 22(1) is exactly ?? restricted to the prime setting; 11 extends it to arbitrary \(\Delta\)-triples with \(n = xyz\).

Let’s see some examples of applying 22. If \(p = 2\), then \(2 q r \in \mathbb{N}(\Delta)\) if and only if \((r - 1)(q - 1) = 3\) (1) or \((q, r) \in \{(4, 5), (3, 4)\}\) (2). Note that (1) implies \(q - 1 = 1\), which contradicts \(p < q\). Regarding (2), we see there are no pairs of primes. Therefore, we conclude that \(2 q r \notin \mathbb{N}(\Delta)\). This is consistent with 15, of which 22 is a particular case when \(p = 2\). If \(p = 3\), then \(3 q r \in \mathbb{N}(\Delta)\) if and only if \((r - 2)(q - 2) = 7\) (1) or \((q, r) = (5, 7)\) (2). We see that (1) implies \(q - 2 = 1\), which contradicts \(p < q\). Thus, \(3 q r \in \mathbb{N}(\Delta)\) if and only if \((q, r) = (5, 7)\), by (2). If \(p = 5\), then \(5 q r \in \mathbb{N}(\Delta)\) if and only if \((r - 4)(q - 4) = 21\) (1) or \((q, r) \in \{(7, 11), (9, 13)\}\) (2). Since \(1 < q - 4 < \sqrt{21} < 5\), it follows from (1) that \(q - 4 = 3\) and \(r - 4 = 7\). Hence, \(5 q r \in \mathbb{N}(\Delta)\) if and only if \((q, r) = (7, 11)\). Similarly, it is very easy to verify that \(7 q r \in \mathbb{N}(\Delta)\) if and only if \((q, r) = (13, 19)\). We can summarize all this in the following corollary.

The next corollary generalizes some arguments used in the previous examples.

The numbers 13, 67, and 79 are the smallest primes satisfying the hypotheses of 11.

Recall that \(\tau:\mathbb{N}\to\mathbb{N}\) denotes the divisor counting function, \(\tau(n)=|D_n|\), which is multiplicative and satisfies \(\tau(p_1^{a_1}\cdots p_k^{a_k})=\prod_{i=1}^k(a_i+1)\), provided \(p_i\) is prime for all \(i\in[k]\). Then, the obstructions established along this section admit the following consequence for \(\tau\).

5.5 Returning to split graphs↩︎

Finally, we close this section with an important theorem about the \(n\)-simple induced cycles of \(\Phi\), when \(n \notin \mathbb{N}(\Delta)\) and is not a square.

It is natural to ask for an arithmetic invariant governing the induced \(4\)-cycles of \(\Phi(S)\), playing the role that the \(\Delta\) property plays for the type 0 triangles. The orientation type of a \(4\)-cycle analogous to \(\Delta_0\) is the directed cycle on \(a, b, c, d\) with arcs \(ab\), \(bc\), \(cd\) and \(ad\): a single arc \(ad\) short-circuits the directed path \(abcd\), so that the degree increase (in \(S\)) from \(a\) to \(d\) equals the sum of the three increases along the path. Determining the condition on \(n\) that characterizes the realizability of such an \(n\)-simple \(4\)-cycle (the \(C_4\) analogue of the \(\Delta\) property) is, as far as we know, uncharted territory, and we leave it as a direction for future work.

Acknowledgements↩︎

This work was partially supported by Universidad Nacional de San Luis, grants PROICO 03-0723 and PROIPRO 03-2923, MATH AmSud, grant 22-MATH-02, Consejo Nacional de Investigaciones Científicas y Técnicas grant, PIP 11220220100068CO and Agencia I+D+I grants PICT 2020-00549 and PICT 2020-04064.

References↩︎