Rearrangement inequality #
This file proves the rearrangement inequality.
The rearrangement inequality tells you that for two functions f g : ι → α
, the sum
∑ i, f i * g (σ i)
is maximized over all σ : perm ι
when g ∘ σ
monovaries with f
and
minimized when g ∘ σ
antivaries with f
.
Implementation notes #
In fact, we don't need much compatibility between the addition and multiplication of α
, so we can
actually decouple them by replacing multiplication with scalar multiplication and making f
and g
land in different types.
As a bonus, this makes the dual statement trivial. The multiplication versions are provided for
convenience.
The case for monotone
/antitone
pairs of functions over a linear_order
is not deduced in this
file because it is easily deducible from the monovary
API.
Scalar multiplication versions #
Rearrangement Inequality: Pointwise scalar multiplication of f
and g
is maximized when
f
and g
vary together. Stated by permuting the entries of g
.
Rearrangement Inequality: Pointwise scalar multiplication of f
and g
is maximized when
f
and g
vary together. Stated by permuting the entries of f
.
Rearrangement Inequality: Pointwise scalar multiplication of f
and g
is minimized when
f
and g
antivary together. Stated by permuting the entries of g
.
Rearrangement Inequality: Pointwise scalar multiplication of f
and g
is minimized when
f
and g
antivary together. Stated by permuting the entries of f
.
Rearrangement Inequality: Pointwise scalar multiplication of f
and g
is maximized when
f
and g
vary together. Stated by permuting the entries of g
.
Rearrangement Inequality: Pointwise scalar multiplication of f
and g
is maximized when
f
and g
vary together. Stated by permuting the entries of f
.
Rearrangement Inequality: Pointwise scalar multiplication of f
and g
is minimized when
f
and g
antivary together. Stated by permuting the entries of g
.
Rearrangement Inequality: Pointwise scalar multiplication of f
and g
is minimized when
f
and g
antivary together. Stated by permuting the entries of f
.
Multiplication versions #
Special cases of the above when scalar multiplication is actually multiplication.
Rearrangement Inequality: Pointwise multiplication of f
and g
is maximized when f
and
g
vary together. Stated by permuting the entries of g
.
Rearrangement Inequality: Pointwise multiplication of f
and g
is maximized when f
and
g
vary together. Stated by permuting the entries of f
.
Rearrangement Inequality: Pointwise multiplication of f
and g
is minimized when f
and
g
antivary together. Stated by permuting the entries of g
.
Rearrangement Inequality: Pointwise multiplication of f
and g
is minimized when f
and
g
antivary together. Stated by permuting the entries of f
.
Rearrangement Inequality: Pointwise multiplication of f
and g
is maximized when f
and
g
vary together. Stated by permuting the entries of g
.
Rearrangement Inequality: Pointwise multiplication of f
and g
is maximized when f
and
g
vary together. Stated by permuting the entries of f
.
Rearrangement Inequality: Pointwise multiplication of f
and g
is minimized when f
and
g
antivary together. Stated by permuting the entries of g
.
Rearrangement Inequality: Pointwise multiplication of f
and g
is minimized when f
and
g
antivary together. Stated by permuting the entries of f
.