<p>Not an answer to your exact question, but may be useful if you happen to have a semiring with cancellation: if you have an algorithm which works in any ring, you can apply that algorithm to the difference ring $S-S$ consisting of subtraction pairs $s - t$.  The result will have the form $s - t$ where $s,t \in S$, and the answer will be $d \in S$ s.t. $s = d + t$.  Thus, in addition to semiring operations, you'd need to perform a single cancellation step at the end.</p>

CC BY-SA 3.0
2013-02-15T21:51:23.290Z
A difference ring can be defined only for a semiring with the cancellation property with respect to addition (x+z=y+z ⇒ x=y).  For example, the (min, +) semiring on ℕ∪{∞} does not have the cancellation property.  Therefore, I do not think that this trick works.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-15T20:58:36.527Z
2013-02-15T21:58:34.430Z
2013-02-15T21:58:34.430Z
Geoffrey Irving
<p>Let <span class="math-container">$S$</span> be a commutative semiring and <span class="math-container">$T\subset S$</span>, how many semiring operations are required to compute the following
<span class="math-container">$$\prod_{a,b\in T} a+b$$</span>?</p>
<p>This problem can be solved for commutative rings in <span class="math-container">$O(n \log n)$</span> ring operations using multipoint polynomial evaluation from <a href="https://math.stackexchange.com/questions/304687/can-product-of-all-pairwise-sums-be-computed-faster-than-the-naive-method">a related problem</a>. However, the algorithm requires there is an inverse to addition.</p>
<p>Actually I'm mostly interested in a similar problem. We have <span class="math-container">$M = \{A_1,\ldots,A_k\}$</span> such that <span class="math-container">$A_i\subset S$</span>. We want to compute</p>
<p><span class="math-container">$$\prod_{A\in M} \prod_{A\neq B\in M} \prod_{a\in A,b\in B} a+b$$</span></p>
<p>with least number of semiring operations.</p>

<ds.algorithms><algebra>
Number of operations to compute product of pairwise sums over a commutative semiring
Chao Xu
# Number of operations to compute product of pairwise sums over a commutative semiring

(Asked by: username_0 on 2013-02-15)

Let $S$ be a commutative semiring and $T\subset S$, how many semiring operations are required to compute the following
$$\prod\_{a,b\in T} a+b$$?

This problem can be solved for commutative rings in $O(n \log n)$ ring operations using multipoint polynomial evaluation from [a related problem](https://math.stackexchange.com/questions/304687/can-product-of-all-pairwise-sums-be-computed-faster-than-the-naive-method). However, the algorithm requires there is an inverse to addition.

Actually I'm mostly interested in a similar problem. We have $M = \{A\_1,\ldots,A\_k\}$ such that $A\_i\subset S$. We want to compute

$$\prod\_{A\in M} \prod\_{A\neq B\in M} \prod\_{a\in A,b\in B} a+b$$

with least number of semiring operations.

**Tags:** ds.algorithms, algebra


---

## 1 answers

### Answer by username_1 on 2013-02-15. Score: 1

Not an answer to your exact question, but may be useful if you happen to have a semiring with cancellation: if you have an algorithm which works in any ring, you can apply that algorithm to the difference ring $S-S$ consisting of subtraction pairs $s - t$. The result will have the form $s - t$ where $s,t \in S$, and the answer will be $d \in S$ s.t. $s = d + t$. Thus, in addition to semiring operations, you'd need to perform a single cancellation step at the end.

> **Comments:**
> **username_2**: A difference ring can be defined only for a semiring with the cancellation property with respect to addition (x+z=y+z ⇒ x=y).  For example, the (min, +) semiring on ℕ∪{∞} does not have the cancellation property.  Therefore, I do not think that this trick works.  

---

