AdditiveEnergy

The number of quadruples $(a_1,a_2,b_1,b_2)\in A\times A\times B\times B$ with $a_1+b_1=a_2+b_2$ .

mathlib4Finset.addEnergy

AdditiveEnergy(A, B)

E(A,B)=\#\{(a_1,a_2,b_1,b_2): a_1+b_1=a_2+b_2\}

, the pairs of pairs with equal sums.

AdditiveEnergy(A)

E(A,A)

.

Typed signatures

Type	Package	Applies
`(collection, collection?) -> integer`	`combinatorics`	always

Domain: Collections

Details

Defined in Epsil as $\sum_x r(x)^2$ , where $r(x)$ is the number of pairs $(a,b)\in A\times B$ with $a+b=x$ : two pairs with the same sum are one quadruple, so tallying the $|A||B|$ sums is enough and the $|A|^2|B|^2$ quadruples are never tested.
The members are the distinct members of the collection, as in mathlib's Finset: a list's repeats are ignored, and a Set reads like a list.
Members must be exact rationals. A float, a symbol or an infinite collection leaves the call unevaluated, since a sum of floats would be tallied by rounding.
At most $|A||B|\min(|A|,|B|)$ , since a sum has at most that many representations, and a subgroup reaches $|A|^3$ . A Sidon set has the least for its size, $2|A|^2-|A|$ ; large energy is what marks a set as additively structured.
$E(\{1,\dots,n\})=(2n^3+n)/3$ , and an arithmetic progression, translated or dilated, has the same energy.
Symmetric in its two arguments, and unchanged by translating either set.
Not a Wolfram, SymPy or Sage head. MultiplicativeEnergy is the same count for products.

Examples

1 more kept as data, checked against the oracles

Basic #

the quadruples of $\{1,\dots,5\}$ with $a_1+b_1=a_2+b_2$

In

\mathrm{AdditiveEnergy}(\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack)

Out

85

$A=\{1,2,3\}$ and $B=\{1,2\}$ have sums $2,3,3,4,4,5$ , so $1+4+4+1$

In

\mathrm{AdditiveEnergy}(\bigl\lbrack1, 2, 3\bigr\rbrack, \bigl\lbrack1, 2\bigr\rbrack)

Out

10

Scope #

one member gives one quadruple

In

\mathrm{AdditiveEnergy}(\bigl\lbrack7\bigr\rbrack)

Out

1

no members, no quadruples

In

\mathrm{AdditiveEnergy}(\bigl\lbrack\bigr\rbrack)

Out

0

a $Set$ is read the same way as a list

In

\mathrm{AdditiveEnergy}(\lbrace1, 2, 3\rbrace)

Out

19

repeats are ignored: the members are $\{1,2,3\}$

In

\mathrm{AdditiveEnergy}(\bigl\lbrack1, 1, 2, 3\bigr\rbrack)

Out

19

exact rationals count too; this is $\{1,2,3\}$ scaled by $\tfrac12$

In

\mathrm{AdditiveEnergy}(\bigl\lbrack\frac{1}{2}, 1, \frac{3}{2}\bigr\rbrack)

Out

19

a translate of $\{1,\dots,5\}$

In

\mathrm{AdditiveEnergy}(\bigl\lbrack-2, -1, 0, 1, 2\bigr\rbrack)

Out

85

Properties #

a Sidon set: all sums $a+b$ with $a\le b$ differ, so only the trivial quadruples remain, $2|A|^2-|A|$

In

\mathrm{AdditiveEnergy}(\bigl\lbrack1, 2, 5, 10, 16\bigr\rbrack)

Out

45

also Sidon: $2\cdot 4^2-4$

In

\mathrm{AdditiveEnergy}(\bigl\lbrack1, 2, 4, 8\bigr\rbrack)

Out

28

an arithmetic progression has the energy of $\{1,\dots,4\}$ , $(2\cdot 4^3+4)/3$

In

\mathrm{AdditiveEnergy}(\bigl\lbrack3, 5, 7, 9\bigr\rbrack)

Out

44

swapping the two sets changes nothing

In

\mathrm{AdditiveEnergy}(\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack1, 2, 3\bigr\rbrack)

Out

10

About

Examples	13
Checked against	mathlib4 13 agree
Crosswalk	mathlib4

Implementation

mappedmathlib4packages/oracle/src/mappings.ts

mathlib's energy is over Finsets, so each list is read as a Finset of rationals (duplicates collapse, as ours do)

mappedmathlib4packages/oracle/src/mappings.ts

mathlib's energy is over Finsets, so each list is read as a Finset of rationals (duplicates collapse, as ours do)

See also: MultiplicativeEnergy, Tally, Unique