Symmetric Polynomials in Upper-bound Semirings
Sara Kališnik Davorin Lešnik
math.AC

	
	[
    [
    December 30, 2023
=====================



	
		The fundamental theorem of symmetric polynomials over rings is a classical result which states that every unital commutative ring is fully elementary, we can express symmetric polynomials with elementary ones in a unique way. The result does not extend directly to polynomials over semirings, but we do have analogous results for some special semirings, for example, the tropical, extended and supertropical semirings. These all fall into a larger class of upper-bound semirings. In this paper we extend the known results and give a complete characterization of fully elementary upper-bound semirings. We further improve this characterization statement in the case of linearly ordered upper-bound semirings.
	
	
	
	

§ INTRODUCTION

	
		The fundamental theorem of symmetric polynomials states that any symmetric polynomial in variables x_1,… , x_n over a unital commutative ring can be represented in a unique way as a polynomial in the elementary symmetric polynomials,
		
    1(x_1, …, x_n)     = x_1 +… + x_n
    2(x_1, …, x_n)    = x_1 x_2 + x_1 x_3 + x_2 x_3 + … + x_n-1 x_n,
    ⋮
    n(x_1, …, x_n)    = x_1 x_2 … x_n.
	
		
		This theorem has an interesting history <cit.>: Newton already extensively studied symmetric root polynomials as early as the mid-1660s, and was very likely aware of the fundamental theorem at that time. Over the course of the eighteenth century many mathematicians seemed familiar with it and used it. For example, Lagrange claimed it was `self-evident'. The existence part of the proof only appeared in 1771, when Vandermonde stated and proved the result in terms of roots and coefficients of a polynomial. The uniqueness aspect was still neglected at the time. The first complete proof is due to Dedekind.
		
		Given the long tradition and the impact of this theorem it is surprising that the question of elementarity over semirings (the ability to express symmetric polynomials with elementary ones) only recently started being researched. The first paper on the topic analyzed the tropical semiring <cit.>. The motivation for doing that came from the study of persistent homology <cit.>, a method which assigns a barcode, a collection of intervals, to a finite metric space and can be used as a measurement of the shape of data. Studying symmetric tropical functions turned out to be crucial in identifying well-behaved coordinates on the space of barcodes <cit.>.
		
		A positive result in the case of the tropical semiring led to a discussion about what happens in other semirings of interest to tropical algebraists, such as the symmetrized max-plus semiring <cit.>, the extended tropical semiring <cit.>, the supertropical semiring <cit.>. In <cit.> we proved that supertropical semirings, including the extended tropical semiring, are elementary. The symmetrizations of the tropical and max-plus semiring, however, are not. 
		
		All of these semirings are upper-bound, so in <cit.> we already presented some partial results about elementarity for upper-bound semirings, though we have not yet obtained a proper characterization result. This is one of the main contributions of this paper.  
		
		This manuscript is organized as follows. In Section <ref> we review the basic definitions needed to state and prove theorems. In Section <ref> we study elementarity in upper-bound semirings. The central result in this section is Theorem <ref>, which gives a complete characterization of fully elementary upper-bound semirings as the Frobenius ones. In Section <ref> we consider linearly ordered upper-bound semirings and improve the characterization in this case. In Section <ref> we consider what the scope of our results is from the perspective of general unital commutative semirings, rather than just the upper-bound ones.
	
	
	

§ PRELIMINARIES

	
		Recall that (X,+,0,·) is a semiring when (X,+,0) is a commutative monoid, (X,·) a semigroup, the multiplication · distributes over the addition + and 0 is an absorbing element, 0 · x = x · 0 = 0 for all x ∈ X. A semiring is unital when it has the multiplicative unit 1. A semiring is commutative when · is commutative. A semiring is idempotent when + is idempotent, x + x = x for all x ∈ X. A map between semirings is a semiring homomorphism when it preserves addition, additive unit and multiplication. If its domain and codomain are unital semirings, it is called a unital semiring homomorphism when it additionally preserves the multiplicative unit.
		
		We often omit the · sign in algebraic expressions, and shorten the product of n many factors x to x^n. Also, we write X instead of (X,+,0,·) (or (X,+,0,·,1)) when the operations are clear.
		
		Given a unital semiring X, we can view any natural number[We treat 0 as a natural number, so = {0, 1, 2, 3, …}.] n ∈ as an element of X in the usual way:
		
    n = 1 + 1 + … + 1_n times.

		However, this mapping (in fact, a unital semiring homomorphism) from  to X need not be injective; for example, if (and only if) X is idempotent, we have 1 = 2 in X.
		
		In this paper we almost exclusively deal with unital commutative semirings which we shorten to uc-semirings.
		
		Any commutative monoid X, and thus in particular any semiring, has an intrinsic order ≤ (see <cit.> ), given by
		
    a ≤ b xXa + x = b.

		The intrinsic order is a preorder (reflexive and transitive) with 0 a least element. The operations + and · are monotone: if a ≤ b and c ≤ d, then a + c ≤ b + d and a · c ≤ b · d. Also, any semiring homomorphism is monotone with respect to the intrinsic order.
		
		The following are the two most crucial properties of ≤ that we use in this paper. First, the intrinsic order is directed, in the sense that any two elements a, b ∈ X have an upper bound, namely a + b. In other words, adding summands increases the sum. The second crucial property for us is antisymmetry of ≤. We do not have it in general, though, so we recall the definition <cit.>.
		
		
			A semiring is upper-bound when its intrinsic order is antisymmetric (thus a partial order).
		
		
		A simple example of an upper-bound semiring is the set of natural numbers , where the intrinsic order is the usual one. Note also that every idempotent semiring is upper-bound.
		
		Recall that any preorder ≤ defines an equivalence relation by
		
    a ≈ b   a ≤ b  b ≤ a.

		A preorder is (by definition) antisymmetric (hence, a partial order) when ≈ is equality. In general, a preorder on a set X induces a partial order on the quotient set X/_≈. If X is a semiring and ≤ its intrinsic order, then ≈ is a congruence (that is, if a ≈ b and c ≈ d, then a + c ≈ b + d and a · c ≈ b · d), meaning that we can turn any semiring into an upper-bound semiring by taking the quotient X/_≈.
		
		There is, of course, no shortage of non-upper-bound semirings. For example, if X is a ring, then for every a, b ∈ X we have a ≤ b (and so a ≈ b). Thus the only upper-bound ring is the trivial one {0}.
		
		We now turn our attention to polynomials over semirings.
		
		
			Let X be a uc-semiring.
			
				
  * Let m, n, d_1,1, …, d_m,n be natural numbers and a_1, …, a_m ∈ X. A monomial is a syntactic object of the form a_k ∏_j = 1^n x_j^d_k,j. A polynomial is a sum of monomials ∑_k = 1^m a_k ∏_j = 1^n x_j^d_k,j. In this paper we only consider polynomials over commutative semirings, so we treat polynomials as equal if they differ only in the order of summands and/or factors.
				
  * A polynomial function is the function X^n → X that a polynomial represents.
				
  * A polynomial is symmetric when for each monomial a_k ∏_j = 1^n x_j^d_k,j in it and each permutation σ∈ S_n the monomial a_k ∏_j = 1^n x_σ(j)^d_k,j also appears in it, up to a change of the order of factors.[That is, we consider symmetry relative to commutativity of multiplication. For example, the polynomial x y is symmetric: the transposition of variables gives y x which we identify with x y. Of course, it would not make sense to consider x y symmetric over a non-commutative semiring.] A polynomial function is symmetric when it can be represented by a symmetric polynomial.
			
		
		
		
			There are two reasonable definitions of when a polynomial function is symmetric: if it is represented by a symmetric polynomial (let us say that a function is `syntactically symmetric' in this case), or if its values are invariant under arbitrary permutations of variables, that is, p(x_1, …, x_n) = p(x_σ(1), …, x_σ(1)) for all (x_1, …, x_n) and permutations σ∈ S_n (say that p is `semantically symmetric'). Every syntactically symmetric polynomial function is semantically symmetric, but we do not know whether the converse holds (for more on the subject, see <cit.> ). For the purposes of our theorems, a `symmetric polynomial function' refers to syntactic symmetry (as stated in Definition <ref>), since our proofs require considering polynomials on the syntactic level. 
		
		
		Let us have a more formal description of a symmetric polynomial (function). For any n ∈ and d = (d_1, …, d_n) ∈^n consider the following subset of the symmetric group S_n:
		
    S_n^d π∈ S_n[1]i, j{1, …, n}(d_i = d_j  i ≤ j) π(i) ≤π(j).

		Then define the minimal symmetric segment, corresponding to d, as
		
    (d) ∑_π∈ S_n^d∏_j = 1^n x_π(j)^d_j.

		The idea is that (d) represents the minimal polynomial which is symmetric and has monomials in which the exponents of variables are given by d. For example, we have (2,1) = x_1^2 x_2 + x_2^2 x_1 and (1,1) = x_1 x_2. However, for the sake of legibility we prefer to use variables x, y, … instead of x_1, x_2, … in concrete cases such as these, so we write for example (2,2,0,0) = x^2 y^2 + x^2 z^2 + x^2 w^2 + y^2 z^2 + y^2 w^2 + z^2 w^2.
		
		Clearly (d) does not change if we permute the terms of d, so whenever necessary we can assume without loss of generality that d is a decreasing sequence. This is helpful since if we view  as a map from finite decreasing sequences to polynomials, it is injective.
		
		So how many terms does (d) have? From each group of terms which differ only by the order of factors we choose a single term (specifically, the one with the exponents in the order, given by d, and in which among the same exponents the variables have increasing indices). For example, (2,1) = x_1^2 x_2 + x_2^2 x_1 contains one of the terms x_1^2 x_2, x_2 x_1^2 and one of the terms x_2^2 x_1, x_1 x_2^2. In essence, we are considering the permutations of multisets. That is, if we split d into blocks of equal terms and the sizes of these blocks are k_1, …, k_j, then |S_n^d| = n!/k_1! k_2! … k_j!.
		
		The crucial observation here is the following: a polynomial (or a polynomial function) p over a unital commutative semiring X is symmetric if and only if it can be written as a linear combination of minimal symmetric segments, in the sense that
		
    p(x_1, …, x_n) = ∑_k = 1^m a_k  (d_k)

		for some m ∈, a_1, …, a_m ∈ X and d_1, …, d_m ∈^n.
		
		Recall that the fundamental theorem of symmetric polynomials over rings states that every symmetric polynomial function over a ring can be represented by a polynomial in elementary symmetric polynomials. Our main purpose in this paper is to prove a similar version of this theorem for upper-bound semirings.
		
		
			Let X be a uc-semiring.
			
				
  * For any n ∈ and k ∈_≤ n the corresponding elementary symmetric polynomial is defined as
					
    k(x_1, …, x_n) (1, …, 1_k  many, 0, …, 0_n-k  many).

					In other words, the elementary symmetric polynomials are precisely the minimal symmetric segments, given by (decreasing) finite binary sequences.[Note that 0 is the constant 1, and thus generally uninteresting in this context.]
				
  * Given n ∈, we say that X is n-elementary when for every symmetric polynomial p in n variables there exists a polynomial r in n variables, such that
					
    p(x_1, …, x_n) = r(1(x_1, …, x_n), …, n(x_1, …, x_n))

					for all x_1, …, x_n ∈ X at the level of polynomial functions.
				
  * X is fully elementary when it is n-elementary for all n ∈.
			
		
		
		Obviously, any uc-semiring is 0-elementary and 1-elementary. Note that higher elementarity implies lower one.
		
		
			Let a uc-semiring X be n-elementary. Then it is also m-elementary for all m ∈_≤ n.
		
		
		
			It suffices to show for any n ∈ that if X is (n+1)-elementary, it is also n-elementary. To this end, take any symmetric polynomial p in n variables in X; we can write it in the form
			
    p(x_1, …, x_n) = ∑_k = 1^m a_k (d_k,1, …, d_k,n).

			Define
			
    q(x_1, …, x_n, x_n+1) ∑_k = 1^m a_k (d_k,1, …, d_k,n, 0).

			Then q is symmetric as well, so by assumption there exists a polynomial r with
			
    q(x_1, …, x_n+1) = r([n+1]1(x_1, …, x_n+1), …, [n+1]n+1(x_1, …, x_n+1)).

			We get
			
    p(x_1, …, x_n) = q(x_1, …, x_n, 0) =

			
    = r([n+1]1(x_1, …, x_n, 0), …, [n+1]n(x_1, …, x_n, 0), x_1 … x_n · 0) =

			
    = r(1(x_1, …, x_n), …, n(x_1, …, x_n), 0) =

			
    = s(1(x_1, …, x_n), …, n(x_1, …, x_n))

			for s(x_1, …, x_n)  r(x_1, …, x_n, 0).
		
	
	
	

§ ELEMENTARITY IN UPPER-BOUND SEMIRINGS

	
		In <cit.> we showed that in idempotent semirings full elementarity is equivalent to the fulfillment of Frobenius equalities, with the purpose to have a characterization of elementarity for the tropical semiring and semirings related to it. In this section we significantly generalize this result to upper-bound semirings.
		
		Recall that the Frobenius equality for the exponent n ∈ in a uc-semiring X states that (x + y)^n = x^n + y^n for all x, y ∈ X. The Frobenius equality for 0 states 1 = 1 + 1, so it is equivalent to the idempotency of the semiring, but we do not want to restrict ourselves to those. As such, we consider only the Frobenius equalities for positive exponents.
		
		
			A uc-semiring X is Frobenius when it satisfies Frobenius equalities for all n ∈_≥ 1.
		
		
		Putting natural numbers into Frobenius equalities reveals some properties of a Frobenius semiring. We prepare a lemma for later.
		
		
			Let X be a unital semiring.
			
				
  * If 2 = 3 in X, then 2 = 4 in X.
				
  * If 2 = 4 in X and X is upper-bound, then 2 = 3 in X.
				
  * If X is Frobenius, then 2 = 4 in X.
			
		
		
		
			
				
  * Add 1 to the equality 2 = 3 and conclude 2 = 3 = 4.
				
  * We have 2 ≤ 2 + 1 = 3 ≤ 3 + 1 = 4 = 2. Since X is upper-bound, we infer 2 = 3.
				
  * Calculate 2 = 1^2 + 1^2 = (1 + 1)^2 = 4.
			
		
		
		Note that if indeed 2 = 4 in a unital semiring X, then any two m, n ∈_≥ 2 are equal whenever they have equal parity. If 2 = 3, then all m, n ∈_≥ 2 are equal in X.
		
		We can now formulate and prove the first step towards the general theorem classifying elementarity in upper-bound uc-semirings. We calculate the product between an elementary symmetric polynomial k and a minimal symmetric segment with at most k non-zero exponents. It is instructive to start with an example.
		
		
			
    (3,2,0,0) ·(1,1,0,0) =

			
    = (x^3 y^2 + x^3 z^2 + x^3 w^2 + y^3 x^2 + y^3 z^2 + y^3 w^2 + z^3 x^2 + z^3 y^2 + z^3 w^2 + w^3 x^2 + w^3 y^2 + w^3 z^2) ·

			
    · (x y + x z + x w + y z + y w + z w) =

			
    (evaluate the 72 terms, collect them together to form minimal symmetric segments)

			
    = (4,3,0,0) + (4,2,1,0) + 2 ·(3,3,1,0) + (3,2,1,1) =

			
    = (3+1,2+1,0,0) + (3+1,2,0+1,0) + 2 ·(3,2+1,0+1,0) + (3,2,0+1,0+1)

		
		
		The point is, the product of (3,2,0,0) and (1,1,0,0) can be expressed as a linear combination (with natural numbers as coefficients) of minimal symmetric segments of sequences that we get by adding the terms of permutations of (3,2,0,0) and (1,1,0,0) and ordering the result to a decreasing sequence.
		
		Consider now the general case. Let X be a uc-semiring, n ∈, k ∈{1, …, n} and d = (d_1, …, d_n) ∈^n a decreasing sequence, for which all non-zero terms appear among the first k terms (meaning, either k = n or k < n and d_k+1 = 0).
		
		For each j ∈{k, …, n} define I^d_j to be the set of those binary sequences α∈{0, 1}^n, such that:
		
			
  * α has exactly k many 1s (therefore n-k many 0s),
			
  * the index of the last 1 in α is j,
			
  * the (componentwise) sum d + α is a decreasing sequence.
		
		Note that then for any α∈ I^d_j and any i ∈ with k < i ≤ j we have α_i = 1.
		
		Now, the polynomial (d) ·k is a product of two symmetric polynomials, and is therefore symmetric itself, meaning that we can write it as a linear combination of minimal symmetric segments. Consider an arbitrary term x_π(1)^d_1… x_π(n)^d_n from (d) and an arbitrary term x_ρ(1)… x_ρ(k) from k. Their product is the product of powers of variables, n-k many of which have the exponent of the form d_i and the remaining k have the exponent of the form d_i + 1. We can always order the exponents decreasingly, so each such product of monomials appears in (d + α) for some j ∈{k, …, n} and α∈ I^d_j. A particular product of monomials can appear several times, but that number is necessarily a natural number since the coefficients of monomials in (d) and k are all equal to 1. That is, we have
		
    (d) ·k = ∑_j = k^n ∑_α∈ I^d_j a_j,α (d + α)

		for some a_j,α∈. Clearly every monomial in (d + α) can actually be obtained, so necessarily a_j,α≥ 1. Furthermore, note that there is only one way to get a term from (d + α) when j = k, so we can write
		
    (d) ·k = (d_1 + 1, …, d_k + 1, 0, …, 0) + ∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α).

		
		We summarize our conclusions in the following lemma.
		
		
			Let X be a uc-semiring, n ∈, k ∈{1, …, n} and d = (d_1, …, d_n) ∈^n a decreasing sequence, for which all non-zero terms appear among the first k terms. Then
			
    (d) ·k = (d_1 + 1, …, d_k + 1, 0, …, 0) + ∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α)

			for some a_j,α∈_≥ 1.
		
		
		We now restrict ourselves to Frobenius semirings.
		
		
			Let X be an upper-bound Frobenius semiring and n ∈_≥ 2. Then
			
    x^n + x^n-1 y + y^n  =  x^n + y^n

			for all x, y ∈ X.
		
		
		
			Since X is Frobenius, we have
			
    x^n + y^n ≤ x^n + x^n-1 y + y^n ≤∑_k = 0^n nk x^n-k y^k = (x + y)^n = x^n + y^n.

			Since X is upper-bound, we conclude x^n + y^n = x^n + x^n-1 y + y^n.
		
		
		In Frobenius semirings we can symplify the formula from Lemma <ref> significantly. To demonstrate how, we first continue the example from before, and afterwards prove the general result.
		
		
			Recall from Example <ref> that
			
    (3,2,0,0) ·(1,1,0,0) = (4,3,0,0) + (4,2,1,0) + 2 ·(3,3,1,0) + (3,2,1,1).

			We claim that, assuming the Frobenius property, we can eliminate all minimal symmetric segments on the right-hand side save the first one. We start from the back.
			
			The first term in (3,2,1,1) is x^3 y^2 z w. We also have terms x^4 y^2 z and w^4 y^2 z in the earlier segment (4,2,1,0). With Lemma <ref> we can calculate
			
    x^4 y^2 z + x^3 y^2 z w + w^4 y^2 z = y^2 z (x^4 + x^3 w + w^4) = y^2 z (x^4 + w^4) = x^4 y^2 z + w^4 y^2 z.

			We have managed to eliminate one term of (3,2,1,1) and with the same kind of reasoning we can eliminate others as well, removing this segment altogether.
			
			Next, consider the term x^3 y^3 z from (3,3,1,0). We can eliminate it with the terms x^4 y^3 and z^4 x^3 from (4,3,0,0). The segment (3,3,1,0) (and in particular the term x^3 y^3 z) is multiplied by 2, but we can just do the elimination twice. Considering also other relevant permutations of variables, we eliminate the whole 2 ·(3,3,1,0).
			
			Finally, eliminate x^4 y^2 z in (4,2,1,0) with the help of terms x^4 y^3 and x^4 z^3 from (4,3,0,0), and similarly for the rest of (4,2,1,0). In the end we get just (3,2,0,0) ·(1,1,0,0) = (4,3,0,0).
		
		
		We now tackle the general case.
		
		
			Let X be an upper-bound Frobenius semiring, n ∈, k ∈{1, …, n} and d = (d_1, …, d_n) ∈^n a decreasing sequence, for which all non-zero terms appear among the first k terms. Then
			
    (d) ·k = (d_1 + 1, …, d_k + 1, 0, …, 0).

		
		
		
			By Lemma <ref> we have
			
    (d) ·k = (d_1 + 1, …, d_k + 1, 0, …, 0) + ∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α)

			for some a_j,α∈_≥ 1. If k = n, we are done, so assume hereafter that k < n.
			
			We claim that we can remove the summands with j ≥ k+1, first for the largest j, then working down. Here is one step of the procedure. Take any j with k+1 ≤ j ≤ n and any α∈ I^d_j. Let i ∈{1, …, n} denote the first index, for which α_i = 0. Such i exists because k < n, and we have i < j since j ≥ k+1. Define β to be the same finite binary sequence as α, except with the i-th and j-th term switched. Observe that then β∈ I^d_j-1.
			
			Consider any monomial x_π(1)^d_1 + α_1… x_π(n)^d_n + α_n in (d + α). Let ρ denote the same permutation as π, except with the i-th and j-th value switched. Then both x_π(1)^d_1 + β_1… x_π(n)^d_n + β_n and x_ρ(1)^d_1 + β_1… x_ρ(n)^d_n + β_n appear in (d + β).
			
			Since a_j-1,β≥ 1, we can “borrow” these two terms from a_j-1,β (d + β); denoting
			
    P  x_π(1)^d_1 + α_1… x_π(1)^d_i-1 + α_i-1· x_π(i)^d_j· x_π(1)^d_i+1 + α_i+1… x_π(1)^d_j-1 + α_j-1· x_π(j)^d_j· x_π(1)^d_j+1 + α_j+1… x_π(1)^d_n + α_n

			and using Lemma <ref>, we get
			
    x_π(1)^d_1 + β_1… x_π(n)^d_n + β_n  +   x_π(1)^d_1 + α_1… x_π(n)^d_n + α_n  +   x_ρ(1)^d_1 + β_1… x_ρ(n)^d_n + β_n =

			
    = P ·(x_π(i)^d_i - d_j + 1 + x_π(i)^d_i - d_j x_π(j) + x_π(j)^d_i - d_j + 1) = P ·(x_π(i)^d_i - d_j + 1 + x_π(j)^d_i - d_j + 1) =

			
    = x_π(1)^d_1 + β_1… x_π(n)^d_n + β_n  +   x_ρ(1)^d_1 + β_1… x_ρ(n)^d_n + β_n.

			The term x_π(1)^d_1 + α_1… x_π(n)^d_n + α_n has vanished! If we do that for all terms in (d + α), we have effectively decreased a_j,α by one, while only using terms from (j-1)-segments (which remained unchanged). Keep doing that for all j between k+1 and n from largest to smallest until all those a_j,α are reduced to zero. In the end, we are left with just
			
    (d) ·k = (d_1 + 1, …, d_k + 1, 0, …, 0).

		
		
		
			Let X be an upper-bound Frobenius semiring, n ∈ and d = (d_1, …, d_n) ∈^n a decreasing sequence. Then
			
    (d) = 1^d_1 - d_2·…·n-1^d_n-1 - d_n·n^d_n.

		
		
		
			Use Lemma <ref> as an induction step to first factor out n from (d) as many times as possible (which is d_n many), then n-1 from the remainder as many times as possible (which is d_n-1 - d_n), and so on. In the end we are left with (0, …, 0), which is equal to 1.
		
		
		We are now ready to prove the central theorem in the paper.
		
		
			The following statements are equivalent for any upper-bound uc-semiring X.
			
				
  * X is Frobenius.
				
  * X is fully elementary.
				
  * X is n-elementary for some n ∈_≥ 2.
				
  * X is 2-elementary.
			
		
		
		
			
				
  * (1  2)
					Any symmetric polynomial can be written as a linear combination of minimal symmetric segments, and any such segment can be written as a product of elementary symmetric polynomials by Lemma <ref>.
				
  * (2  3)
					By definition.
				
  * (3  4)
					By Proposition <ref>.
				
  * (4  1)
					Take any n ∈_≥ 1. The polynomial x^n + y^n is symmetric, so by assumption we can write
					
    x^n + y^n = ∑_k = 1^m a_k (x y)^i_k (x + y)^j_k.

					This holds for all x, y ∈ X, and we can choose to set y to 0 and replace x with x + y which gives us
					
    (x + y)^n = ∑_k ∈{1, …, m}, i_k = 0 a_k (x + y)^j_k.

					Hence
					
    x^n + y^n ≤∑_k = 0^n nk x^n-k y^k = (x + y)^n = ∑_k ∈{1, …, m}, i_k = 0 a_k (x + y)^j_k≤

					
    ≤∑_k = 1^m a_k (x y)^i_k (x + y)^j_k = x^n + y^n

					(note that we needed n ≥ 1 for the first step in this chain). X is upper-bound, so we conclude x^n + y^n = (x + y)^n.
			
		
		
		In short, an upper-bound uc-semiring is fully elementary if and only if it is Frobenius. It is important that the semiring is upper-bound — we do not have the equivalence in general. According to the fundamental theorem of symmetric polynomials over rings, all uc-rings are elementary, but they are not Frobenius in general (take for example the ring of real numbers ). We discuss this more in detail in Section <ref>.
	
	
	

§ ELEMENTARITY IN LINEARLY ORDERED SEMIRINGS

	
		In the previous section we characterized the fully elementary upper-bound semirings as the Frobenius ones. However, many interesting upper-bound semirings are linearly ordered[Recall that X is linearly ordered by ≤ when all x, y ∈ X are comparable, x ≤ y or y ≤ x.] by their intrinsic order — in fact, our starting motivation was to study elementarity in semirings such as the tropical and the extended tropical semiring, which are linearly ordered. In this section we improve the characterization for such semirings.
		
		To set the stage, we first recall the basic facts about the ghost ideal <cit.>, defined for any semiring X as the subset of elements which satisfy the idempotency condition:
		
    νXa ∈ Xa = a + a.

		Clearly 0 ∈νX and if a, b ∈νX, then a + b ∈νX. Also, if a ∈νX and x ∈ X, then x · a ∈νX and a · x ∈νX. In short, νX is indeed a semiring ideal in X. We can now immediately conclude from the definition that νX is an idempotent semiring.
		
		Define the map ν X → X by ν(x)  x + x. Clearly ν is an additive monoid homomorphism, although it is not necessarily a semiring homomorphism (take for example X =). Also, ν is a monotone map (with regard to the intrinsic order) and we have x ≤ν(x) for all x ∈ X.
		
		By definition, νX is the set of fixed points of ν. Note that if X is unital (so we have natural numbers in X), we can write ν(x) = 2x and νX = a ∈ Xa = 2a.
		
		The consideration of ghost ideals arose from the study of supertropical semirings <cit.>, which we will get to shortly. But first, a more general notion.
		
		
			A semiring X is quasiidempotent when x + x + x + x = x + x for all x ∈ X.
		
		
		Clearly ν can be used to characterize quasiidempotent semirings.
		
		
			Let X be a semiring. The following statements are equivalent.
			
				
  * X is quasiidempotent.
				
  * ν is a projection (ν∘ν = ν).
				
  * The image of ν is νX.
				
  * The image of ν is an idempotent subsemiring in X.
			
		
		
		
			Easy.
		
		
		When we have a multiplicative unit, we can extend the characterization of quasiidempotent semirings.
		
		
			Let X be a unital semiring. The following statements are equivalent.
			
				
  * X is quasiidempotent.
				
  * 2 = 4 in X.
				
  * ν is a semiring homomorphism.
				
  * νX has a multiplicative unit and the restriction ν X →νX is a unital semiring homomorphism.
			
		
		
		
			
				
  * (1  2)
					Apply quasiidempotency for the unit 1.
				
  * (2  1)
					If 2 = 4, then 2x = 4x for any x ∈ X.
				
  * (2  3)
					We know that ν is an additive monoid homomorphism. It remains to check that ν preserves multiplication: ν(x) ·ν(y) = 2x · 2y = 4xy = 2xy = ν(xy).
				
  * (3  2)
					2 = ν(1) = ν(1 · 1) = ν(1) ·ν(1) = 2 · 2 = 4.
				
  * (2  3  4)
					We have ν(1) = 2 and 2 ·ν(x) = 4x = 2x = ν(x).
				
  * (4  3)
					Yes.
			
		
		
		Quasiidempotent semirings are useful because they allow us to view X as a bundle[Here we use the term `bundle' in the most general sense — as any map, where we treat the domain as a disjoint union of fibers.] over νX, with ν as the bundle projection. This bundle has a section νX↪ X and both ν and this inclusion preserve the semiring operations and the intrinsic order. This allows us to pass between the total space and the base of the bundle, often reducing issues from X to the more manageable (since it is an idempotent semiring) νX.
		
		In light of this view, let us examine fibers of ν closer.
		
		
			Let X be a quasiidempotent semiring.
			
				
  * Given a ∈ X, the fiber ν^-1(a) is non-empty if and only if a ∈νX. In that case a is the largest element of ν^-1(a).
				
  * Suppose X is upper-bound. For any x ∈ X and a ∈νX, if x ≤ a, then x + a = a.[As a special case, when X is idempotent (therefore upper-bound, 1 = 2 and νX = X), we get that a ≤ b  a + b = b for all a, b ∈ X.]
			
		
		
		
			
				
  * Suppose we have x ∈ν^-1(a); then 2a = 4x = 2x = a, so a ∈ν^-1(a). Conversely, if a = 2a, then a ∈ν^-1(a).
					
					Take any x ∈ν^-1(a). Then x ≤ 2x = a.
				
  * Since x ≤ a, there exists y ∈ X with x + y = a. We then have
					
    a ≤ x + a ≤ 2x + 2a = 4x + 2y = 2x + 2y = 2a = a.

					Since X is upper-bound, we conclude a = x + a.
			
		
		
		We now recall the definition of supertropical semirings <cit.>.
		
		
			A supertropical semiring X is a quasiidempotent uc-semiring which satisfies the following for all a, b ∈ X:
			
				
  * if ν(a) ≠ν(b), then a + b ∈{a, b},
				
  * if ν(a) = ν(b), then a + b = ν(a) = ν(b).
			
		
		
		Finally, we get to linearly ordered upper-bound semirings. In fact, the intrinsic order is the only order on semirings that we consider in this paper; thus, any time we refer to a linearly ordered semiring, we mean linearly ordered by its intrinsic order.
		
		In any linearly ordered upper-bound semiring X we can introduce the strict order relation < as one would expect. For a, b ∈ X define a < b in either of the following equivalent ways:
		
    a ≤ b  a ≠ b     ¬(b ≤ a).

		The relation < is irreflexive, asymmetric and transitive. Also, < satisfies the law of trichotomy: for any a, b ∈ X exactly one of the statements a < b, a = b, b < a holds.
		
		
			Let X be a linearly ordered upper-bound quasiidempotent unital semiring.
			
				
  * For any a ∈νX the fiber ν^-1(a) contains either exactly one or exactly two elements.
				
  * For all x, y ∈ X we have x = y if and only if
					
    ν(x) = ν(y)     (x ∈νX y ∈νX).

				
  * If x, y ∈ X, y ∉νX and x < y, then 2x < y.
				
  * For any x, y ∈ X, if x < y, then x + y = y.
			
		
		
		
			
				
  * Since a ∈νX, Lemma <ref> tells us that a is the largest element of ν^-1(a). Suppose we had at least two further elements x, y ∈ν^-1(a); without loss of generality assume x < y < a. Then there exists u ∈ X such that x + u = y. It follows that 2u ≤ 2y = a, but we cannot have 2u = a since that would mean u ∈ν^-1(a) and then y = x + u ≥ 2 min{x,u} = a (since in a linear order min{x,u}∈{x,u}). Thus 2u < a. If x ≤ 2u, then a = 2x ≤ 4u = 2u < a, a contradiction, so 2u < x. Then there exists v ∈ X such that 2u + v = x. Lemma <ref> gives us 2 = 3, and we get a contradiction y = x + u = 3u + v = 2u + v = x.
				
  * Follows easily from the previous item.
				
  * Suppose 2x ≥ y; then 2x = 4x ≥ 2y. On the other hand x ≤ y implies 2x ≤ 2y, so 2x = 2y. But ν^-1(2y) = {y, 2y} and x < y < 2y, a contradiction.
				
  * If y ∈νX, then x + y = y by Lemma <ref>. Assume now y ∉νX; then by the previous item 2x < y. We have some u ∈ X with x + u = y. Certainly u ≤ y. Suppose u < y; then 2u < y. Since 2x, 2u ∈νX, Lemma <ref> tells us that 2y = 2x + 2u ∈{2x, 2u}. In either case we get 2y < y, a contradiction. Hence u = y, meaning that y = x + u = x + y.
			
		
		
		We can now show that when a semiring is linearly ordered, elementarity (as well as supertropicality) reduces to a simple comparison of two numbers.
		
		
			The following statements are equivalent for any linearly ordered upper-bound uc-semiring X.
			
				
  * The equivalent statements of Theorem <ref> hold for X (in particular, X is fully elementary).
				
  * X is supertropical.
				
  * X is quasiidempotent.
				
  * 2 = 3 in X.
			
		
		
		
			
				
  * (1  3)
					Lemma <ref> tells us that the Frobenius property of X implies 2 = 4 in X.
				
  * (1  3  2)
					Take any a, b ∈ X. If a = b, then a + b = 2a = ν(a). Otherwise without loss of generality a < b, so a + b = b ∈{a, b} by Lemma <ref>.
				
  * (2  3)
					By definition.
				
  * (3  1)
					We prove the Frobenius equality for any n ∈_≥ 1. Take x, y ∈ X; since X is linearly ordered, we may without loss of generality assume x ≤ y. If x = y, then
					
    (x + y)^n = (2x)^n = 2^n x^n = 2 x^n = x^n + y^n.

					On the other hand, if x < y, then x + y = y by Lemma <ref>. Hence
					
    x^n + y^n ≤∑_k = 0^n nk x^n-k y^k = (x + y)^n = y^n ≤ x^n + y^n.

					Since X is upper-bound, we conclude (x + y)^n = x^n + y^n.
				
  * (3  4)
					By Lemma <ref> the statements 2 = 4 and 2 = 3 are equivalent in our situation.
			
		
	
	
	

§ TOWARDS GENERAL CHARACTERIZATION OF ELEMENTARITY

	
		The previous two sections established the main results of the paper. This section, on the other hand, is more speculative. We consider what the scope of our results is — we look at them from the perspective of general uc-semirings, rather than just the upper-bound ones.
		
		Recall that Theorem <ref> tells us that full elementarity is equivalent to the Frobenius property for upper-bound uc-semirings. Clearly, we do not have such an equivalence for general uc-semirings. By the fundamental theorem of symmetric polynomials over rings, every unital commutative ring is fully elementary. Of course, not every uc-ring is Frobenius.[There is a reason why the Frobenius equalities (x + y)^n = x^n + y^n are informally called “Freshman's Dream”.] There is a simple characterization for when it is.
		
		
			A uc-ring X is Frobenius if and only if x · y · (x + y) = 0 for all x, y ∈ X.
		
		
		
			
				
  * ()
					Suppose X is a Frobenius ring. We have 2 = 4 by Lemma <ref>, and we can subtract 1 on both sides to get 1 = 3. Thus
					
    x^3 + y^3 = (x + y)^3 = x^3 + 3 x^2 y + 3 x y^2 + y^3 = x^3 + x^2 y + x y^2 + y^3 = x^3 + x y (x + y) + y^3.

					Subtracting x^3 + y^3 on both sides yields the desired equation.
				
  * ()
					First apply the assumed equation for x = y = 1 to get 2 = 0. Take now any n ∈_≥ 1; we prove the Frobenius equality for the exponent n by induction on n. Of course, the Frobenius equality for n = 1 always holds.
					
					As for the induction step, assume that the Frobenius equalities hold for exponents, smaller than n (but larger than 0). We have (x + y)^n = ∑_k = 0^n nk x^n-k y^k. If n is even, we have the middle binomial coefficient nn/2 = n-1n/2 - 1 + n-1n/2 = 2 ·n-1n/2 which is even, so equal to 0 in X. All other terms (regardless of the parity of n) come in pairs, and for 0 < k < n/2 we have
					
    nk x^n-k y^k + nn-k x^k y^n-k = nk (x y)^k (x^n-2k + y^n-2k) =

					
    = nk (x y)^k (x + y)^n-2k = x y (x + y) nk (x y)^k-1 (x + y)^n-2k-1 = 0.

					Thus what we are left with is (x + y)^n = n0 x^n + nn y^n = x^n + y^n.
			
		
		
		Thus not every fully elementary semiring is Frobenius. What about the other implication? We do not yet know the answer, so we pose this as a question.
		
		
			Is every Frobenius semiring fully elementary?
		
		
		The problem with answering such a question is that, at least in rings, and presumably in many other semirings as well, the Frobenius property is entirely incidental to elementarity. On the other hand, it proved to be crucial for upper-bound semirings. We now make it explicit why this was the case.
		
		
			Let X be a uc-semiring. The following statements are equivalent.
			
				
  * X is Frobenius and 2 = 3 in X.
				
  * X satisfies the statement of Lemma <ref>.
				
  * X satisfies the statement of Lemma <ref>
				
  * X satisfies the statement of Lemma <ref>
				
  * For every n ∈ the map  is a monoid homomorphism from the additive monoid of decreasing sequences of length n to the multiplicative monoid of polynomial functions in n variables over X.
			
		
		
		
			
				
  * (1  2)
					We reprove Lemma <ref>, but this time only under the assumption that X is Frobenius and 2 = 3 in X.
					
					Take any x, y ∈ X and n ∈_≥ 2. Then n1 = n = n + 1 in X. By Frobenius we get
					
    x^n + y^n = (x + y)^n = ∑_k = 0^n nk x^n-k y^k =

					
    = x^n-1 y + ∑_k = 0^n nk x^n-k y^k = x^n-1 y + (x + y)^n = x^n + x^n-1 y + y^n.

				
  * (2  3)
					Note that the proof of Lemma <ref> does not use the fact that X is upper-bound directly. It relies on Lemma <ref> (applicable for general uc-semirings) and Lemma <ref>.
				
  * (3  4)
					The proof of Lemma <ref> does not use the upper-boundedness of X directly. It relies on Lemma <ref>.
				
  * (4  5)
					By assumption we have (d) = 1^d_1 - d_2·…·n-1^d_n-1 - d_n·n^d_n for any decreasing d ∈^n. Applying this for d', d”, d' + d”, we get
					
    (d' + d”) =  1^(d'_1 + d”_1) - (d'_2 + d”_2)·…·n-1^(d'_n-1 + d”_n-1) - (d'_n + d”_n)·n^d'_n + d”_n =

					
    = (1^d'_1 - d'_2·…·n-1^d'_n-1 - d'_n·n^d'_n) ·(1^d”_1 - d”_2·…·n-1^d”_n-1 - d”_n·n^d”_n) = (d') ·(d”).

				
  * (5  1)
					Take any n ∈_≥ 1 and x, y ∈ X. We get[One can make the case that this argument is the essence, why we do not include n = 0 in the Frobenius property (Definition <ref>): (n,0) has two terms for n ≥ 1, and only one for n = 0.]
					
    x^n + y^n = (n,0) = ((1,0) + … + (1,0)) = (1,0) ·…·(1,0) = ((1,0))^n = (x + y)^n.

					Thus X is Frobenius, and Lemma <ref> tells us that therefore natural numbers, greater than or equal to 2, are the same in X if they have equal parity. Hence
					
    2 = 6 = (2,1,0)(1,1,1) = (1,0,0)(1,1,1) ·(1,1,0)(1,1,1) = 3 · 3 = 9 = 3.

			
		
		
		In view of the last of the equivalent statements of the lemma, we introduce the following definition.
		
		
			A uc-semiring is symhomomorphic when it satisfies the equivalent statements of Lemma <ref>.
		
		
		The point is that it is the symhomomorphic property which captures the essence of the idea of the proof of elementarity in this paper. In fact, we can distill the results of Section <ref> into the following corollary.
		
		
			Let X be a uc-semiring.
			
				
  * If X is upper-bound and Frobenius, it is symhomomorphic.
				
  * If X is symhomomorphic, it is fully elementary.
			
		
		
		
			
				
  * By Lemmas <ref> and <ref>.
				
  * The proof of (1  2) in Theorem <ref> relies only on Lemma <ref>.
			
		
		
		Of course, this is just the part that Frobenius implies full elementarity. Theorem <ref> states that for upper-bound semirings the converse is also true. How critical is the upper-boundedness for this argument?
		
		
			For upper-bound uc-semirings the Frobenius property and full elementarity are equivalent. Is there a larger natural class of semirings where this is still true?
		
		
		At first glance one might be optimistic and speculate that between characterizations of full elementarity in upper-bound uc-semirings and in uc-rings, one will get a characterization for general uc-semirings. The point is that upper-bound semirings are in a sense “orthogonal” to rings. We have already mentioned that the only upper-bound ring is the trivial one. Moreover, for every semiring X (and the aforementioned equivalence relation a ≈ b  a ≤ b  b ≤ a) we have a short exact sequence
		
    {0}→ [0] ↪ X ↠ X/_≈→{0}

		where X/_≈ is an upper-bound semiring and the equivalence class [0] = x ∈ X0 ≈ x is a ring. That is, any uc-semiring can be split into an upper-bound semiring and a uc-ring in this way.
		
		Unfortunately, this approach turns out to be rather limited. Exact sequences are useful for categories which are abelian (or at least additive), which semirings decidedly are not. In particular, it is not even true that if [0] is trivial, X is necessarily upper-bound.
		
		A simple example is _2=4/_ where  has the usual semiring operations and  is the smallest congruence such that 2  4 (that is, we identify any numbers ≥ 2 which have the same parity). The underlying set of _2=4 is {[0], [1], [2], [3]}, and we have [0] ≤ [1] ≤ [2] ≤ [3] ≤ [2]. The uc-semiring _2=4 is Frobenius, but not upper-bound or symhomomorphic.
		
		Is it fully elementary? It turns out that the answer is yes. Recall from Lemma <ref> that
		
    (d) ·k = (d_1 + 1, …, d_k + 1, 0, …, 0) + ∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α).

		In _2=4 we can transfer the big sum to the other side of the equation:
		
    (d_1 + 1, …, d_k + 1, 0, …, 0) = (d) ·k + ∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α)

		(it turns out that when a term in the big sum is not zero, the numbers are large enough that only parity matters).
		
		From here a suitable induction allows us to reduce all minimal symmetric segments to polynomials in elementary symmetric polynomials. In fact, the argument is essentially the same as in the fundamental theorem of symmetric polynomials over rings, where we get
		
    (d_1 + 1, …, d_k + 1, 0, …, 0) = (d) ·k - ∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α)

		and proceed from there.
		
		Recall from Lemma <ref> that in the case of Frobenius upper-bound uc-semirings we were able to write
		
    (d_1 + 1, …, d_k + 1, 0, …, 0) = (d) ·k + 0 ·∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α).

		Is the ability to write these expressions in these forms merely a coincidence or is there something more to it?
		
		
			Is it the case for every fully elementary semiring X that we have
			
    (d_1 + 1, …, d_k + 1, 0, …, 0) = (d) ·k + u ·∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α)

			for some u ∈ X?
		
		
		Above we made the case for this question by examples, but a theoretical case can also be made. If we drop the upper-boundedness condition, the proof of (4  1) in Theorem <ref> still tells us that x^n + y^n ≈ (x + y)^n for all n ∈ and x, y ∈ X where X is a fully elementary (or at least 2-elementary) uc-semiring. Take n = 2 and x = y = 1 to get 2 ≈ 4. Hence 2 ≤ 3 ≤ 4 ≤ 2, so also 2 ≈ 3. Thus there exists u ∈ X such that 3 + u = 2.
		
		The idea is that this kind of u might “play the role of -1” sufficiently well. The solution to the equation 3 + u = 2 may not be unique, but with some luck, given any
		
    (d) ·k = (d_1 + 1, …, d_k + 1, 0, …, 0) + ∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α)

		(as per Lemma <ref>), we could find a solution which allows us to take the big sum to the other side of the equation:ž
    (d_1 + 1, …, d_k + 1, 0, …, 0) = (d) ·k + u ·∑_j = k+1^n ∑_α∈ I^d_j a_j,α(d + α).

		From here, we could derive full elementarity by induction.
		
		Recall that Theorem <ref> says (among other things) that a linearly ordered upper-bound uc-semiring is fully elementary if and only if 2 = 3 holds in it. A positive answer to the following question would be a significant generalization.
		
		
			Is the condition 2 ≈ 3 in a uc-semiring not just a necessary, but also a sufficient condition for full elementarity?
		
		
		Of course, this entire discussion is just an aspect of a more general question.
		
		
			Is there a meaningful theorem which classifies elementarity for arbitrary uc-semirings?
		
		
		
		

