TITLE: If directional derivatives are bounded, then function is continuous
QUESTION [1 upvotes]: Suppose we have $f:S\to \mathbb R$ where $S$ is the open unit circle:
  $S=\lbrace (x,y)\in \mathbb R ^{2} \mid x^2 +y^2 <1\rbrace $, and suppose
  $\vec v, \vec w$ are two independent unit vectors.
Suppose $\exists C>0,\forall \vec z\in S,\Bigl|\frac {\partial f}{\partial v}(z)\Bigr|<C,\Bigl|\frac {\partial f}{\partial w}(z)\Bigr|<C$.
Show that $f$ is continuous in $S$.

Now, I know that if the partial derivatives exist and bounded, then $f$ is continous, but I'm having trouble expressing the partial derivatives in terms of the given directional derivatives. Of course $e_x=(1,0)$ can be expressed as a linear combination of $v,w$, but how can I formally apply it to $\frac{\partial f}{\partial x}$?

REPLY [1 votes]: Here is a more complete proof. However, I think the basic idea gets lost in
the details.
Let $A= \begin{bmatrix}v & w \end{bmatrix}$ and define $\phi(z) = f(A z)$ on the open convex set $\Sigma=A^{-1} S$. Note that
${\partial \phi(z) \over \partial z_1} = {\partial f(Az) \over \partial u}$
and ${\partial \phi(z) \over \partial z_2} = {\partial f(Az) \over \partial w}$.
The key element of the proof is that for any $z_1,z_2 \in \Sigma$, we can choose (because $\Sigma$ is open & convex) a path $y_1=z_1 \to y_2\to \cdots \to y_{n-1} \to y_n = z_2$ such that each segment of the path is parallel to either axis and the direction of each segment is the same (with respect to the corresponding axis).
In particular, if $V_j(y) = [y]_j$ we have
$V_j(z_2-z_1) = \sum_k V_j(y_k-y_{k-1})$, for a given $j$, all of the $V_j(y_k-y_{k-1})$ have the same sign and at most one of
$V_1(y_k-y_{k-1}) $ or $V_2(y_k-y_{k-1})$  are
non zero. Hence $|V_j(z_2-z_1)| = \sum_k |V_j(y_k-y_{k-1})|$.
Note that on each segment, we can apply the mean value theorem to get
$|\phi(y_k)-\phi(y_{k-1})| \le C (|V_1(y_k-y_{k-1}) | + |V_2(y_k-y_{k-1})| )$ and
so
\begin{eqnarray}
|\phi(z_2)-\phi(z_1)| &\le& \sum_k |\phi(y_k)-\phi(y_{k-1})| \\
&\le & C \sum_k(|V_1(y_k-y_{k-1}) | + |V_2(y_k-y_{k-1})| ) \\
&=& C(|V_1(z_2-z_1)| + |V_2(z_2-z_1)|) \\
&=& C \|z_2-z_1\|_1
\end{eqnarray}
Finally, we return to '$f$' space:
$|f(z_2)-f(z_1)| = |\phi(A^{-1} z_2) - \phi(A^{-1} z_1)| \le C \|A^{-1}(z_2-z_1)\|_1 \le C\|A^{-1}\|_1 \|z_2-z_1\|_1$
Hence $f$ is Lipschitz continuous with rank at most $C\|A^{-1}\|_1$.


TITLE: Representation of linear operator
QUESTION [1 upvotes]: Suppose I have a space of cumulative distribution functions on $\mathbb{R}$ denoted $\mathcal{F}$. There is a linear functional $A$ that maps to some subset of $\mathbb{R}$ whose domain is $\mathcal{F}$ and $A$ is sup-norm continuous in $\mathcal{F}$ (i.e. if a sequence $\{F_n\}_{n=1} ^\infty$ in $\mathcal{F}$ converges in the sup-norm then $\{A[F_n]\}_{n=1} ^\infty$ converges).
What I want to know is the following. Can I represent $A$ as follows:
$A[F]=\lim_{k\to\infty} \int a_k(x) dF(a)$ for some sequence of functions $\{a_k\}_{k=1} ^\infty$?
I suppose what I'm really asking is a question about the dual of $L_\infty$ and whether there is a particular dense subset of this space, but I'm not sure. Any help greatly appreciated.

REPLY [0 votes]: I think the following proof works, but I'm not sure.
Let $B_b$ be a functional that returns $B_b[F](z)=\frac{1}{b}\int \phi (\frac{z-x}{b}) dF(x)$ for some constant $b$ where $\phi$ is the standard normal density function. Clearly for any $b$ $B_b[F]$ is $L_1$ with the Lebesgue measure and hence by Radon-Nikodym there must be a function $a$ such that $A[B_b[F]]=\int a(x) B_b[F](x) dx$, and so we have:
$A[B_b[F]]=\int a(x) \frac{1}{b}\int \phi (\frac{x-z}{b}) dF(z) dx= \frac{1}{b}\int \int a(x) \phi (\frac{x-z}{b})  dxdF(z)$
And so we see that:
$A[F]=\lim_{b\to 0} \frac{1}{b}\int \int a(x) \phi (\frac{x-z}{b})  dxdF(z)$
I've not been very careful coming up with that so some of the steps might be wrong.


TITLE: Electrostatic Force between 2 charged bodies
QUESTION [2 upvotes]: A thin spherical non-conducting sphere of radiua R carries uniform surface charge density ($\sigma $ ).It is cut into two parts by a plane at a distance R/√2 from center as shown. To hold two parts together force F has to be applied. Find force F ? (assume charge dosen't redistribute after cutting)
The answer provided by my textbook uses the concept of electrostatic pressure to find force on one part(electeostatic pressure at any point on sphere is $ \sigma^2 $/2$ \epsilon° $). But the electrostatic pressure at any point is due to whole sphere  and we have to calculate force on part 1 only due to part 2(we have considered force due to elements of part 1 on itself also). Is my textbook correct ? If not can anyone suggest any other way to solve it?

REPLY [2 votes]: Your textbook is correct. For electrostatic forces, Newton's third law is valid. Hence, the net force acting on part one from part one is zero. The same is correct for part two.


text:
section \<open>Standard gates\<close>

theory Gates
  imports Complex_Matrix
begin

text \<open>Pauli matrices\<close>
definition sigma_x :: "complex mat" where
  "sigma_x = mat_of_rows_list 2 [[0, 1], [1, 0]]"

definition sigma_y :: "complex mat" where
  "sigma_y = mat_of_rows_list 2 [[0, -\<i>], [\<i>, 0]]"

definition sigma_z :: "complex mat" where
  "sigma_z = mat_of_rows_list 2 [[1, 0], [0, -1]]"

text \<open>Hadamard matrices\<close>
definition hadamard :: "complex mat" where
  "hadamard = mat 2 2 (\<lambda>(i, j). if (i = 0 \<or> j = 0) then 1 / csqrt 2 else - 1 / sqrt 2)"

lemma hadamard_dim:
  "hadamard \<in> carrier_mat 2 2"
  unfolding hadamard_def mat_of_rows_list_def by auto

lemma hermitian_hadamard:
  "hermitian hadamard"
  unfolding hermitian_def hadamard_def
  apply (rule eq_matI) by (auto simp add: adjoint_eval adjoint_dim)

lemma csqrt_2_sq:
  "complex_of_real (sqrt 2) * complex_of_real (sqrt 2) = 2"
  by (smt of_real_add of_real_hom.hom_one of_real_power one_add_one power2_eq_square real_sqrt_pow2)

lemma sum_le_2:
  "\<And>(f::nat\<Rightarrow>complex). sum f {0..<2} = f 0 + f 1"
  by (simp add: numeral_2_eq_2)

lemma unitary_hadamard:
  "unitary hadamard"
  unfolding unitary_def apply (rule)
  subgoal using carrier_matD[OF hadamard_dim] hadamard_def by auto
  apply (subst hermitian_hadamard[unfolded hermitian_def])
  unfolding inverts_mat_def
  apply (rule eq_matI) unfolding hadamard_def
    apply (auto simp add: carrier_matD[OF hadamard_dim] scalar_prod_def)
  by (auto simp add: sum_le_2 csqrt_2_sq)

text \<open>The matrix
  [0 0 .. 0 1
   1 0 .. 0 0
   0 1 .. 0 0
   . . .. . .
   0 0 .. 1 0]
  implements i := i + 1 in the last variable.
\<close>
definition mat_incr :: "nat \<Rightarrow> complex mat" where
  "mat_incr n = mat n n (\<lambda>(i,j). if i = 0 then (if j = n - 1 then 1 else 0) else (if i = j + 1 then 1 else 0))"

lemma mat_incr_dim:
  "mat_incr n \<in> carrier_mat n n"
  unfolding mat_incr_def by auto

lemma adjoint_mat_incr:
  "adjoint (mat_incr n) = mat n n (\<lambda>(i,j). if j = 0 then (if i = n - 1 then 1 else 0) else (if j = i + 1 then 1 else 0))"
  apply (rule eq_matI) unfolding mat_incr_def
  by (auto simp add: adjoint_eval)

lemma mat_incr_mult_adjoint_mat_incr:
  shows "mat_incr n * (adjoint (mat_incr n)) = 1\<^sub>m n"
  apply (rule eq_matI, simp)
    apply (auto simp add: carrier_matD[OF mat_incr_dim] scalar_prod_def)
  unfolding adjoint_mat_incr unfolding mat_incr_def
   apply (simp_all)
  apply (case_tac "j = 0")
  subgoal for j by (simp add: sum_only_one_neq_0[of _ "n - Suc 0"])
  subgoal for j by (simp add: sum_only_one_neq_0[of _ "j - 1"])
  done

lemma unitary_mat_incr:
  "unitary (mat_incr n)"
  unfolding unitary_def inverts_mat_def
  using carrier_matD[OF mat_incr_dim] mat_incr_mult_adjoint_mat_incr by auto

end

subset_name: curated


TITLE: All tangential Stiefel-Whitney numbers of $\mathbb{R}P^q$ are zero iff $q$ is odd, reference?
QUESTION [6 upvotes]: Where can I find a reference to the proof of the following fact?

All tangential Stiefel-Whitney numbers of $\mathbb{R}P^q$ are zero if and only if $q$ is odd.

I made a quick search through Hatcher but could not find any mention...

REPLY [3 votes]: I don't know of a reference of this fact, but it follows from a collection of well-known results.
First of all, the total Stiefel-Whitney class of $T\mathbb{RP}^q$ is $w(T\mathbb{RP}^q) = (1 + a)^{q+1}$, so $w_i(T\mathbb{RP}^q) = \binom{q+1}{i}a^i$ (as this is an element of $H^i(X, \mathbb{Z}/2\mathbb{Z})$, reduce $\binom{q+1}{i}$ modulo $2$).
If $q$ is even, $w_q(T\mathbb{RP}^q) = \binom{q+1}{q}a^q = (q+1)a = a$, so the corresponding Stiefel-Whitney number is $w_q = \langle w_q(T\mathbb{RP}^q), [\mathbb{RP}^q]\rangle = \langle a^q, [\mathbb{RP}^q]\rangle = 1 \neq 0$. More generally, the top Stiefel-Whitney class is the mod $2$ reduction of the Euler class so the corresponding Stiefel-Whitney number is the Euler characteristic modulo $2$ (in this case $\chi(\mathbb{RP}^q) = 1$).
So the only possible values of $q$ for which all the Stiefel-Whitney numbers of $\mathbb{RP}^q$ can vanish are the odd ones. We still need to show that for all odd values of $q$, the numbers do indeed vanish.
For any $i_1, \dots, i_k$ with $i_1 + \dots + i_k = q$, we have
\begin{align*}
w_{i_1,\dots,i_k} &= \langle w_{i_1}(T\mathbb{RP}^q)\cup\dots\cup w_{i_k}(T\mathbb{RP}^q), [\mathbb{RP}^q]\rangle\\
&= \left\langle\binom{q+1}{i_1}a^{i_1}\cup\dots\cup\binom{q+1}{i_k}a^{i_k}, [\mathbb{RP}^q]\right\rangle\\
&= \binom{q+1}{i_1}\dots\binom{q+1}{i_k}\langle a^q, [\mathbb{RP}^q]\rangle\\
&= \binom{q+1}{i_1}\dots\binom{q+1}{i_k}.
\end{align*}
This is zero if and only if one of the binomial coefficients are even.
To show the existence of some even binomial coefficient in the above product, I need to use the following result: if $n$ is even and $k$ is odd, $\binom{n}{k}$ is even. This follows from Lucas' Theorem which is a useful thing to know when computing Stiefel-Whitney classes/numbers, but there is also a simpler proof. First we start with the identity $k\binom{n}{k} = n\binom{n-1}{k-1}$. As $n$ is even, the right-hand side of the identity is divisible by $2$, and therefore so is the left-hand side. As $k$ is odd, $\binom{n}{k}$ must be divisible by $2$, that is, even.
Returning to the problem at hand, note that if $i_1 + \dots + i_k = q$ and $q$ is odd, there is some $1 \leq j \leq k$ such that $i_j$ is odd. By the above result $\binom{q+1}{i_j}$ is even and hence $w_{i_1,\dots,i_k} = 0$.
So we have established that all the Stiefel-Whitney numbers of $\mathbb{RP}^q$ vanish if and only if $q$ is odd.

By a theorem of Thom and Pontryagin, two closed manifolds are cobordant if and only if they have the same Stiefel-Whitney numbers. In particular, a closed manifold has all Stiefel-Whitney numbers zero if and only if it is the boundary of some compact manifold (i.e. null-cobordant). So, for every odd $q$, there is some compact $(q+1)$-dimensional manifold $X_{q+1}$ with $\partial X_{q+1} = \mathbb{RP}^q$. The manifolds $X_{q+1}$ can actually be determined, see this MathOverflow question.

Added Later: I just realised that the solution I gave above is a less elegant version of the solution outlined in Milnor & Stasheff on page $51$. It may not be suitable as a reference for the highlighted fact in your post though. I have included the relevant excerpt below.

As an example, let us try to compute the Stiefel-Whitney numbers of the projective space $P^n$ (which is about the only manifold we are able to handle at this point). Let $\tau$ denote the tangent bundle of $P^n$. If $n$ is even, then the cohomology class $w_n(\tau) = (n+1)a^n$ is non-zero, and it follows that the Stiefel-Whitney number $w_n[P^n]$ is non-zero. Similarly, since $w_1(\tau) = (n+1)a \neq 0$, it follows that $w_1^n[P^n]\neq 0$. If $n$ is actually a power of $2$, then $w(\tau) = 1 + a + a^n$, and it follows that all other Stiefel-Whitney numbers of $P^n$ are zero. In any case, even if $n$ is not a power of $2$, the remaining Stiefel-Whitney numbers can certainly be computed effectively as products of binomial coefficients.
On the other hand if $n$ is odd, say $n = 2k - 1$, then $w(\tau) = (1 + a)^{2k} = (1+a^2)^k$, so it follows that $w_j(\tau) = 0$ whenever $j$ is odd. Since every monomial of total dimension $2k - 1$ must contain a factor $w_j$ of odd dimension, it follows that all of the Stiefel-Whitney numbers of $P^{2k-1}$ are zero. This gives some indication of how much detail and structure this invariant overlooks.


TITLE: Comparing cardinalities of the spectrum of two masas in $B(H)$
QUESTION [6 upvotes]: If I imagine that (the self-adjoint part of) a C*-algebra $A$ represents the algebra of observables of some quantum system, then certain perspectives on algebraic quantum theory would ask me to imagine that each (maximal) commutative C*-subalgebra $C \subseteq A$ provides a (maximal) "classical snapshot" of this quantum system.  Gelfand duality yields that $C \cong C(X)$ for the compact Hausdorff space $X = \mathrm{Spec}(C)$, so I would picture $X$ as a classical state space that (maximally) "approximates" the would-be quantum state space corresponding to $A$.
I would like to know how different these spaces $X$ can be as the maximal commutative $*$-subalgebra $C \subseteq A$ varies.  Specifically, can it happen that these have different cardinalities?
I'm interested in the particular case $A = B(H)$ for a separable Hilbert space $H$ and two of its well-known masas: the continuous one $C \cong L^\infty[0,1] \subseteq A$ and discrete one $D \cong \ell^\infty(\mathbb{N}) \subseteq A$.  Thus I ask:

Q: Is there a bijection between the Gelfand spectra $\mathrm{Spec}(C)$ and $\mathrm{Spec}(D)$ for the continuous and discrete masas $C,D \subseteq B(H)$?

It's possible to describe these spectra in more explicit terms using Boolean algebra.  Note that each of these masas is an (A)W*-algebra.  By a combination of Gelfand and Stone dualities (see section 2 of this paper for a bit more detail), the spectrum of a commutative AW*-algebra $K$ is the Stone space of the complete Boolean algebra $\mathrm{Proj}(K)$ of projections in $K$, whose points are the ultrafilters of $\mathrm{Proj}(K)$.
The continuous masa $C \cong L^\infty[0,1]$ has $\mathrm{Proj}(C)$ isomorphic to the Boolean algebra of measurable subsets of $[0,1]$ modulo the null sets.  I have just learned through the magic of Wikipedia that this is called the random algebra; I will denote it by $B$.
The discrete masa $D \cong \ell^\infty(\mathbb{N})$ has $\mathrm{Proj}(D)$ isomorphic to the power set Boolean algebra $2^\mathbb{N}$.  (Note that an ultrafilter on the Boolean algebra $2^\mathbb{N}$ is alternatively referred to as an ultrafilter on the set $\mathbb{N}$.)
Thus my question is equivalent to:

Q': Is there a bijection between the sets of ultrafilters on the random algebra $B$ and the power set algebra $2^\mathbb{N}$?

I am aware that $\mathrm{Spec}(D)$ has spectrum homeomorphic to the Stone-Cech compactification $\beta\mathbb{N}$ of the discrete space $\mathbb{N}$, and that this space has various properties that depend on set-theoretic assumptions.  Now that I know what the random algebra is called, I see that it bears a relationship to forcing.  Thus I can imagine that the answer to my question could be independent of ZFC.  Nevertheless, as I am not asking exactly what the cardinality of this spectrum is, but whether it is in bijection with some other (possibly complicated) spectrum, I have an ounce of hope that this can indeed be decided in ZFC.
(By the way, the classification of the possible masas of $B(H)$ implies that, if the answer to my question is affirmative, then the spectra of all masas of $B(H)$ are in bijection with one another.)

REPLY [5 votes]: Yes. The spectra of $\ell_\infty$ and $L_\infty$ have the same cardinality, namely $2^{\mathfrak{c}}$.
Indeed, every infinite, compact $F$-space space (in particular, an extremely disconnected compact space such as the spectrum of $L_\infty$) contains a copy of $\beta \mathbb{N}$ (which happens to be the spectrum of $\ell_\infty$). This is 14N(5) in

L. Gillman and M. Jerison, Rings of continuous functions, van Nostrand Reinhold, New York, 1960.

and it is quite elementary. The Hausdorff–Pospíšil theorem implies that $|\beta\mathbb{N}|=2^{\mathfrak{c}}$. Thus,  $2^{\mathfrak{c}}\leqslant |{\rm spec}\, L_\infty|$.
I claim that the cardinality of ${\rm spec}\, L_\infty$ cannot be bigger than $2^{\mathfrak{c}}$. Indeed, $L_\infty^*$ is a bidual of a separable Banach space, hence by Goldstine's theorem, it is separable in the weak*-topology. Every separable space has cardinality at most $2^{\mathfrak{c}}$. Thus
$|{\rm spec}\, L_\infty|\leqslant |L_\infty^*|\leqslant 2^{\mathfrak{c}}.$


TITLE: What is an elliptic curve, and how are they used in cryptography?
QUESTION [38 upvotes]: I hear a lot about Elliptic Curve Cryptography these days, but I'm still not quite sure what they are or how they relate to crypto...

REPLY [0 votes]: You can see this article as well: www.cs.umd.edu/Honors/reports/ECCpaper.pdf


TITLE: If $f$ is continuous and moderate decreasing, then Fourier transform of $f$ is continuous.
QUESTION [2 upvotes]: If $f$ is continuous and of moderate decrease, show that $\hat{f}$ is continuous.

My attempt:
$$ \hat{f}(\omega+h)-\hat{f}(\omega) = \int_{-\infty}^\infty f(x)e^{-2\pi ix\omega}(e^{-2\pi ix h} - 1) dx $$
I am attempted to pass the limit. Namely,
$$\lim_{h\to 0}\int_{-\infty}^\infty f(x)e^{-2\pi ix\omega}(e^{-2\pi ix h} - 1) dx = \int_{-\infty}^\infty f(x)e^{-2\pi ix\omega} \left(\lim_{h\to 0} (e^{-2\pi ixh} - 1)\right)dx = 0$$
But I suppose since we have an improper integral here, we need to justify it. For simplicity of notation, let $A = f(x)e^{-2\pi i x \omega}$. I start with
$$\lim_{h\to 0}\int_{-L}^L A(e^{-2\pi ixh}-1) dx = \int_{-L}^L A \lim_{h\to 0}(e^{-2\pi ixh}-1) dx=0$$
That means for any $\epsilon >0$ there exists $\delta$ such that
$$x\in (-\delta,\delta) \Longrightarrow \left|\int_{-L}^L A(e^{-2\pi ixh}-1) dx \right| < \epsilon$$
But this doesn't seem to get what I need. Any suggestion? Thank you.

REPLY [1 votes]: I'm not sure what you mean by moderate decrease. I suspect you use an argument such as the following, assuming $f(t)t$ is absolutely integrable, for example:
$$
    \hat{f}(\omega+h)-\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(t)\{e^{-i\omega t}-e^{-i(\omega+h)t}\}dt \\
  =\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(t)\int_{0}^{h}\frac{d}{du}e^{-i(\omega+u)t}du\,dt \\
  =\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(t) (-it)\int_{0}^{h}e^{-i(\omega+u)t}du\,dt \\
  = \int_{0}^{h}\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(t)(-it)e^{-i(\omega+u) t}dt\,du
$$


TITLE: For which values of p and q does an improper integral converge
QUESTION [1 upvotes]: I am to find for which values of p and q the following integral converges:
$$\int_0^\infty \frac{x^p}{1+x^q}\,dx\quad (q>0)$$
As I tested the limit of the above function with $\frac{x^p}{x^q}$, and found it was $1$, I let myself separate the boundaries from $0$ to $1$, and from $1$ to infinity of the later function.
From $0$ to $1$ it's a normal integral, that leaves us to check what the divergence of the integral from $1$ to infinity, which by the comparison test happens as $q>$$1$+$p$
Thanks for the quick replay.

REPLY [1 votes]: Hint : Use the fact that $\zeta(k)=\sum_{n=1}^\infty\frac1{n^k}$ diverges for $k\leqslant1\iff k=q-p>1$ .


TITLE: Irreducible divisor in a basepoint free linear system
QUESTION [3 upvotes]: Let $X$ be a projective, normal variety over complex field with canonical singularities. Suppose $|D|$ is a basepoint free linear system, then is it true that the generic elements in $|D|$ are irreducible?
Besides, I noticed that something might related to "free linear system" (see Mori, Kollár "Birational geometry of algebraic varieties" Page 158, Lemma 5.17). Is "free linear system" the same as basepoint free linear system?

REPLY [4 votes]: Just to illustrate this on a simple example: take on $\mathbb{P}^1\times \mathbb{P}^1$ the divisor $D$ equivalent to $2f$, where $f$ is the fibre of one projection. Then $|D|$ is base-point free but any member is the union of two fibres (computing the intersection with $f$ we get $0$ so it is vertical), so is not irreducible.


TITLE: Proving that $ \mid z+1\mid^{2}=2\mid z\mid^{2} \Leftrightarrow \mid z-1\mid^{2}=2 $
QUESTION [1 upvotes]: Let z be a complex number.
How does one prove, using the properties of the conjugate and the modulus, that:
$$ \mid z+1\mid^{2}=2\mid z\mid^{2}
\Leftrightarrow
\mid z-1\mid^{2}=2 $$

REPLY [0 votes]: An elementary solution:
First, note that $|x+iy|^2=x^2+y^2,|x+1+iy|^2=x^2+2x+1+y^2$, and $|z-1  |^2=(x-1)^2+y^2.$
We have then
$$ x^2+2x+1+y^2=2x^2+2y^2$$
or $$x^2-2x+1-2+y^2=0$$
which is equivalent with the following
$$(x-1)^2+y^2=2$$
and again, this is what we needed
$$|z-1  |^2=2.$$


TITLE: How to understand $|1+z|<1$ where $z\in\mathbb{C}$ geometrically?
QUESTION [0 upvotes]: I am trying to understand how to plot $|1+z|<1$ where $z\in\mathbb{C}$, is it a circle centred at real axis $\text{Re}(z)=-1$ with radius $1$?
My question is how can we show it algebraically?
I tried $|1+z|=|1+a+bi|<1$, then I am not sure how to proceed to make it into equation of a circle?
Another question is what if $|1+z+\frac{z^2}{2}|<1$?
I tried $\Big|1+a+bi+\frac{(a+bi)^2}{2}\Big|=\Big|[1+a+\frac{1}{2}(a^2-b^2)]^2+(b+ab)^2 \Big|<1$? I am not sure whether it is a circle. Any hint?
Could somebody please give some help?
Many thanks!

REPLY [0 votes]: I have no idea why you need an algebraic argument. $|1+z|<1$ means that the distance of the point $z$ from the point $-1$ is less than 1, so $z$ must lie in the open disk centre $-1$ radius 1. But if you put $z=a+ib$, then $|z+1|<1$ is equivalent to $|z+1|^2<1$ is equivalent to $(a+1)^2+b^2<1$ which is the open disk radius $1$, centred at $-1$.
For the second part you probably do need algebra. The same approach gives $(1+a+(a^2-b^2)/2)^2+(b+ab)^2<1$, which gives the interior of an oval around the point $-1$.


TITLE: Using the notation of wedge product to solve a linear system of equations
QUESTION [5 upvotes]: I am trying to solve a problem that seems like a standard idea from linear algebra but with a the notion of wedge product and exterior algebra added it gets more complicated  for someone who isn't very comfortable using the wedge product notation.  Any explanation of the following problem would be greatly appreciated.
Let $\sum_{j=1}^{n} a_{ij} v_j  = b_i$ for $1 \leq i \leq m$ where the system of linear equations is given over an arbitrary commutative ring $R$.  Let $c_j$ be columns of the matrix $(a_{ij}) $.
Suppose that the all minors of the matrix $(a_{ij})$ of order greater than $p$ are zero but that $c_1 \wedge c_2 \wedge \ldots \wedge c_p \neq 0$.
If we let $b = ( b_i)$ then why is it true that for $\sum_{j=1}^{n} a_{ij} v_j  = b_i$ to have a solution for $1\leq i \leq m$ then it is necessary that $c_1 \wedge c_2 \wedge \ldots \wedge c_p \wedge b = 0$?

REPLY [2 votes]: Let me denote your $v_j$ by $x_j$. Assume
$$
\sum_{j=1}^n\ a_{ij}\ x_j=b_i
$$
for all $i$. We can rewrite this as
$$
\sum_{j=1}^n\ x_j\ c_j=b.
$$
We have
$$
c_1\wedge\cdots\wedge c_p\wedge b=\sum_{j=p+1}^n\ x_j\ c_1\wedge\cdots\wedge c_p\wedge c_j=0,
$$
the last equality following from the vanishing of the minors of order greater than $p$.
EDIT. Here is a complement to the Edit in Georges's nice answer. This is Proposition 12, Section III.7.9, of Bourbaki's Algèbre:

Let $M$ be a projective $R$-module, and let $x_1,\dots,x_n$ be in $M$. Then the $x_i$ are linearly dependent if and only if there is a nonzero $r$ in $R$ such that
  $$
r\ x_1\wedge\cdots\wedge x_n=0.
$$

As Georges points out, the condition
$$
x_1\wedge\cdots\wedge x_n\neq0
$$
does not imply that the $x_i$ are linearly independent.
Georges gives an example. Here is a minor variation: take $R:=\mathbb Z/4\mathbb Z$, $n=1$, $x_1=2$.


TITLE: Terminology request: Graphs based on vector spaces
QUESTION [1 upvotes]: I am interested in graphs $G=(V,E)$ with vertex set $V$ a finite dimensional vector space and edges in $E$ which are not necessarily related to the linear structure of $V$. So my objects are just graphs with a vertex set with additional structure, and I don't require any special morphisms. (The vector space structure is for combinatorial reasons, to count vertices in terms of dimension.) I'd like to use a striking name for those graphs, but neither do I know if
1) there is already a name for them,
2) there would be collision with other terminology if I named them something like "vector graphs", "vector based graphs", etc.
For example "linear graph" would be a bad choice.
If some graph theory terminology specialist out there could help that would be very nice.

REPLY [0 votes]: Your situation reminds me of vertex colored graphs, that is graphs whose vertices are colored such that no two vertices of the same color share an edge. (See for example here: http://en.wikipedia.org/wiki/Graph_coloring ) You could then just use the dimension of the vector space associated to a vertex as its color. But it's not clear to me whether you objects satisfy this additional assumption on adjacency.


TITLE: What is the solution for a general case of $ax^m = e^{b/x^n}$?
QUESTION [1 upvotes]: What is the solution for a general case of $ax^m = e^{b/x^n}$?
I am a bit new to non elementary function, but it seems Lambert W function is a probable solution. Upon checking, it seems, it requires some form of symmetry, what if there is no known symmetry? How do we solve this analytically?

REPLY [3 votes]: Let $t:=\dfrac b{x^n}$ and the equation is
$$a\left(\frac bt\right)^{m/n}=e^t$$ or
$$a^{n/m}\frac bt=e^{nt/m}.$$
Now with $s:=\dfrac{nt}m$,
$$a^{n/m}b\frac nm=se^{s}.$$
Finally,
$$x=\sqrt[n]{\frac{nb}{mW\left(a^{n/m}b\dfrac nm\right)}}$$


TITLE: Generation distribution for Poisson offspring
QUESTION [0 upvotes]: If a certain animal has $N$ offspring, with $N$ Poisson distributed, what is the distribution of $Z$, the surviving offspring in the next generation (each offspring has probability p of surviving)? I found online theory about Poisson branching processes and there is a probability generating function mentioned there, but I want to know what the exact distribution is. For uniform distributed offspring it is easy to just multiply $p$ with the mean, but here I have some trouble linking the Poisson distribution to the probability of survival $p$.

REPLY [0 votes]: Do you mean by $Z$ the number of surviving offsprings?
Then $[Z \vert N = n ] \sim$ Bin$(n,p)$ (in words: given $N=n$ the random variable $Z$ has distribution Bin$(n,p)$). This is because for every offspring you are flipping a coin with succes-probability $p$, where the number of offsprings is Poisson distributed.
Hence you will find the answer to your question in Binomial random variable with number of trials being a Poisson random variable.


text:
\begin{document}

\maketitle

\tableofcontents

\section{Introduction}
\label{intro}

The morality of algorithms and their potential for bias and discrimination are important concerns. A popular approach to machine learning and artificial intelligence is via the numerical optimization of objective functions, and adapting such an approach to handle ethics could seem natural: with a hammer in hand, everything looks like a nail. The hammer of much artificial intelligence is the optimization of objective values, so some might like to treat morality solely through such objective functions. However, relying solely on the optimization of scalar objective values is fraught with unavoidable flaws when dealing with real people. Unfortunately, certain ideals in physics, economics, and operations research and optimization fall short in ethics. The purpose of this memo is to highlight obvious, well-known limitations that often get lost in the numbers and mathematical formalism. This memo focuses almost exclusively on descriptive social science, suggesting only a few normative prescriptions in passing. The goal here is to deal with reality as it is, rather than to contemplate what could be the ideal if we were to design society from scratch.

What could we do instead of relying solely on scalar objective values, instead of choosing and targeting a ``metric'' as the sole measure of success? We could emulate the legal and political system, being reasonably reactive and instituting prohibitions, rather than trying to be omniscient and instituting permissions and centralized designs. In the presence of uncertainty, disagreement, and corruption or adversarial activities, setting boundaries can be more robust than trying to optimize objectives within the feasible set of solutions (unless the number of boundary pushers is too great). The key is to react rapidly, reasonably, reliably, resolutely, and righteously.

The problems with relying solely on the optimization of scalar objective values range from the abstract issues of heterogeneity and complicated dynamical systems discussed in Sections~\ref{differences} and~\ref{dynamicals} to the complications of constrained, slow motion and multiple optimizers discussed in Sections~\ref{beyond} and~\ref{multiple} to the realities of uncertainty and psychology discussed in Sections~\ref{reality} and~\ref{scientism}. Sections~\ref{judicial} and~\ref{conclusion} very briefly sketch some possible ways forward. One could argue that any one of the objections discussed below should preclude the optimization of scalar objective values from being good on its own; all together, the objections should be conclusive. Hopefully this addresses an analogue of the droll complaint to Andrei N.\ Kolmogorov reported by~\cite{kendall}: ``You [Kolmogorov] have supplied one proof of your thesis, and in the mathematics that you study this would perhaps suffice, but we historians prefer to have at least ten proofs.'' The basic theme is that the optimization of scalar objective values is insufficient for real people, so (at least insofar as sophisticated algorithms must work and plan around people) the optimization of scalar-valued objective functions cannot possibly be sufficient for ensuring the algorithmic fairness we desire.\footnote{\label{degenerate}Needless to say, for a sufficiently simple problem, optimizing a scalar objective function may be sufficient for a good algorithm to solve that problem. For instance, an algorithm controlling an autonomous vacuum cleaner for floors could integrate well into the home environment despite having only a very simplistic model of morality. In contrast, more sophistication is probably necessary for some of the algorithms powering tech behemoths. Furthermore, this memo considers only sufficiently simple, ``optimizable'' objectives; the memo does not consider any objective that is defined only a posteriori, defined in terms of the results of its own optimization. After all, what use is an objective function which is defined (almost circularly) in terms of its own consequences after optimization? For example, anything can be formulated as maximizing the function defined to take the value 1 for what actually happens and to take the value 0 for every other possibility, but that function is not ``optimizable'' in any useful sense.}

\section{Diversity}
\label{differences}

Sections~\ref{perspectives} and~\ref{values} below review two oft-neglected philosophical truisms, which are central to the discussion; Section~\ref{consequences} sketches some of their consequences. Section~\ref{treatmentVSequity} then highlights a particularly important consequence. The technical literature refers to the observations of Sections~\ref{perspectives} and~\ref{values} as ``epistemological pluralism,'' as discussed by~\cite{turkle-papert}.

\subsection{Different perspectives}
\label{perspectives}
Different perspectives are useful, with potentially consistent, complementary conclusions, even when the premises used to derive those conclusions may be contradictory. The key is to amalgamate the end products of multiple analyses, without needing to reconcile the hypotheses and other means used to obtain those ends.

The classic, uncontroversial example of this from mathematics is the foundations of differential and integral Calculus. The mainstream foundation assumes that there is no positive number less than every finite positive number epsilon; this assumption leads to the delta-epsilon approach of Augustin-Louis Cauchy and Karl Weierstrass (which is related to the ``method of exhaustion'' of Archimedes). An alternative foundation assumes that there do exist positive numbers --- infinitesimals --- less than every finite positive number; this assumption leads to the ``non-standard analysis'' of Abraham Robinson. Both approaches rigorously yield Calculus, though formulating solutions to practical problems is sometimes easier with one of the approaches (which approach is best varies according to the application) \dots\ and the combined results of applying the two approaches offer complementary insights (which is especially helpful when discretizing a continuous formulation in order to perform calculations on a digital computer). The collection of~\cite{arkeryd-cutland-henson} elaborates.

Section~\ref{consequences} below touches upon some consequences for fairness.

\subsection{Different values and localized behaviors}
\label{values}
Different people are different, not only in their values, but also in their behavior conditioned on their values. The extent and sense in which someone is rational or irrational varies from person to person. At the very least, some people are smarter than others, and the range of smarts is actually quite large. Moreover, people generally optimize locally, not globally, leading to ``hysteresis'' (``hysteresis'' is a technical term for ``history-dependent behavior''). For instance, the United States of America has yet to fully adopt the metric system which constitutes the International System of Units; the United States' idiosyncratic customary, traditional system of weights and measures persists largely by maintaining continuity in the historical milieu as an established standard, and deviations from that standard can be painful, whether or not the standard is especially sensible in terms of global optimality. Similarly, people often optimize locally in time (short-term optimization) rather than globally (long-term optimization); taking advantage of delayed gratification is not everyone's forte. The following Section~\ref{consequences} discusses some consequences for fairness.

\subsection{Consequences of these differences}
\label{consequences}
The above-mentioned properties of differences imply that leveraging such diversity can be powerful and that considering such differences is necessary for success. Taking into account the fact that different people are different is essential, whereas homogenization of their axioms and beliefs would be beside the point (and pointless) --- inconsistency of their mindsets is irrelevant so long as their outcomes are mutually agreeable. For example, mathematicians and physicists have long co-existed productively, despite the latter's thinking being so sketchy (well, physicists may object to their thinking being characterized as sketchy, but mathematicians think they know better). Moreover, many computer scientists consider the main purpose of the fast Fourier transform to be the accelerated multiplication of large integers (whereas applications to spectral analysis and spectral methods, such as accelerated convolutional filtering and the numerical solution of differential equations, are probably foremost in most others' minds). A less facetious example is the synergy of abstract theoreticians and concrete experimentalists complementing each other. Really, as transformatively useful as the work of~\cite{sutton-barto} and many others has proven in many situations, unification of everyone into some scalar ``utility'' value, driven by the control theory or reinforcement learning of scalar rewards, turns out to be impossible, unnecessary, and undesirable (due to these properties of differences). Fairness is not just a number.

\subsection{Equity in treatment versus equity in outcome}
\label{treatmentVSequity}
There is no single right answer to what bias and discrimination may mean, or at least no single right answer with which everyone agrees. Some prefer equity in ``treatment''; others prefer equity in ``outcomes.'' ``Treatment'' refers to society's rules governing its members; for instance, society may prefer that laws not explicitly discriminate between a northerner and a southerner. ``Outcomes'' refers to what society's members end up achieving; for example, society may prefer that northerners make the same on average as southerners. Furthermore, the line between ``treatment'' and ``outcome'' is murky: not everyone is the same, with the same access to resources and opportunities, endowed with the same history and abilities. Such differences can be used to argue for either equity in treatment or equity in outcomes, as can various levels and varieties of corruption and of checks and balances. Indeed, those benefiting from inequality in outcomes often argue for equity in treatment, whereas those benefiting from inequality in treatment often argue for equity in outcomes. Unfortunately, the different notions of equity are generally incommensurate, as detailed, for example, by~\cite{pleiss-raghavan-wu-kleinberg-weinberger} and (without all the formal mathematical proofs) by Section B.3
of~\cite{belmont}. There needs to be some sort of balance.

\section{Dynamical systems}
\label{dynamicals}

Sections~\ref{complexs} and~\ref{fittest} present people and societies as dynamical systems, with Section~\ref{complexs} discussing how the real dynamics cannot be formulated as tractable optimizations, aside from the trivial tautology discussed in Section~\ref{fittest}. Sufficiently simple dynamical systems sometimes admit formulations as tractable optimizations; however, the differences discussed in Section~\ref{differences} above quash any hope for the existence or desirability of such a formulation.

\subsection{People and peoples are complex systems}
\label{complexs}
Really, humans are complicated dynamical systems playing the game of life, not optimizing any single scalar-valued objective over time.\footnote{\label{physics}Being part of reality and thus governed by the laws of physics, the closed system constituting the whole universe does always exist at the locally stationary points of the Lagrangian action, at least to the extent that the time evolution is deterministic, as discussed by~\cite{arnold} and~\cite{wald}. Yet humans do not constitute any kind of closed system. Moreover, the very concept of entropy and its maximization depends on a rather arbitrarily defined probabilistic, statistical, or fine-to-coarse multiscale model; notions such as Kolmogorov complexity can avoid some of the arbitrariness in the probabilistic model, but such notions are incomputable (and therefore incomprehensible as principles for falsifiable scientific prediction), as discussed in connection with the second law of thermodynamics (entropy maximization) by~\cite{cover-thomas}.} Society is an even more complex dynamical system. Here, ``dynamical system'' refers simply to how everyone and everything consists of many interacting parts acting rather reflexively and often stochastically to stimuli. For instance, anyone with exquisitely good taste can understand the modern-art and fashion communities only as dynamical systems, not optimal in any way, to the extent that they make any sense at all. Joking aside, formal definitions have been elaborated, for example, by~\cite{bertalanffy} and~\cite{boulding}. Given the complicated dynamics, designing a complete set of understandable laws or algorithms to be consistent, much less optimal according to an agreeable scalar objective value, must be utterly intractable. Different cases require different balances of people's rights.

\subsection{Survival of the fittest and their supporters}
\label{fittest}
Regarding aspirations toward optimality, the nonexistence of any reasonable scalar objective means that the only notion which makes sense for a very complicated dynamical system or game (in the game-theoretic sense) in the long run is ``survival of the fittest,'' where ``fittest'' means ``whatever survives.'' (Yes, that is circular and tautological, as caricatured by~\cite{dawkins}. See also Footnote~\ref{degenerate} in Section~\ref{intro} regarding objective functions defined retrospectively, that is, in hindsight.) The complex dynamics is rather arbitrary and subject to strong dependence on artifacts of history. Admittedly, stability may entail adherence to the basic ethical principle of no exploitation: individuals are responsible for supporting those who make their lifestyle possible. Yet such a principle is only a limited constraint, not fully specifying the behavior. For instance, while extraordinarily commandeered income or wealth inequality may lead to conflict, restricting to more equitable incomes and wealth is only a mild restriction. The non-uniqueness of optima discussed in Section~\ref{pareto} is related. Survival (with or without exploitation) fails to fully specify values being optimized, except after the fact.

\section{Optimization beyond the objective value}
\label{beyond}

Sections~\ref{hysteresis} and~\ref{constrainers} review how the objective value is often less important than other aspects of optimization, such as the dynamics discussed in Section~\ref{hysteresis} and the constraints discussed in Section~\ref{constrainers}. That dynamics and the constraints on those dynamics are important should be unsurprising, given the observation in Section~\ref{dynamicals} above that people and peoples are complex dynamical systems.

\subsection{Hysteresis due to local rather than global optimization}
\label{hysteresis}
Maximizing a scalar objective value is often visualized as riding up and down (but mostly up) the hills and valleys of a landscape, trying to get as high as possible (viewing altitude as the objective value being maximized). The latitude and longitude are coordinates which describe the ``state of the world'' or ``allocation of resources''; to fully describe the whole world requires more than just two numbers (latitude and longitude), of course, but visualizations usually restrict to a small number of dimensions \dots\,anyway, the analogy for a large number of dimensions should be clear. A classic problem in optimization is the tendency to try moving up always, getting stuck at the peaks of small hills rather than sometimes descending in order to reach and ascend larger mountains. Many of the methods for optimization discussed by~\cite{press-teukolsky-vetterling-flannery} target this problem of finding local rather than global optima.

People and societies do tend to get stuck at local optima. The landscape for optimization of those who are optimizing is highly non-convex, that is, there are many hills and valleys of varying heights and depths. Indeed, this non-convexity arises for many reasons, including the nonexistence of convex utility functions for all individuals (discussed below) and the presence of ``market failures'' that can block attainment of a fully efficient equilibrium, creating distortions and hurdles too high to be overcome. Market failures range from ``moral hazard'' and ``information asymmetry'' (for example, salespeople can profit from selling ``lemons'' --- defective products whose defects afflict only the purchasers) to the ``tragedy of the commons'' (overfishing is a perennial problem, for example) to ``externalities'' (pollution is a classic example) to ``outdated best practices'' (bloodletting took millennia to die) to inviolable ``collusion'' (try selling nuclear weapons for other than the government's asking price, for instance) to high ``barriers to entry'' (try starting a copycat competitor to the national postal system, for example). And, as discussed by~\cite{tinbergen}, this is only a small selection of the complications.

Randomness helps ameliorate the tendency to get stuck, yet ``change is hard,'' ``conformity'' (\cite{forsyth}), ``cognitive inertia'' (\cite{good}), ``institutional inertia'' (page 76 of~\cite{tinbergen}), ``myopic decision making'' (\cite{hinson-jameson-whitney}), and ``systemic or systematic risks'' (\cite{hull}) are all commonly discussed phenomena that must be overcome to attain substantial progress. As discussed by~\cite{hinson-jameson-whitney}, few are willing to sacrifice in the short term so as to attain great long-term gains, and fewer still are able to effect the massive broadly coordinated changes often required to move down the molehill surrounding a local maximum and then move up a mountain. Focusing solely on the objective value disregards these necessarily complex dynamics.

\subsection{The overwhelming influence of constraints}
\label{constrainers}
Optimizing locally seldom optimizes globally. As reviewed by~\cite{stiglitz-walsh}, classical economics often considers the world ``ceteris paribus'' --- ignoring how constraints such as existing capital development and distribution, technology, social structures, etc.\ come about. However, those constraints usually do more to affect the outcome than any optimization within the constraints. Who doubts that the prominence of Coca Cola has much to do with development of its brand? And what is more important to wireless communications than control of the airwaves or the technology to use them? Without the development of modern technology, we would still mostly be farmers, if not hunter-gatherers. Another example is how the state of medicine and regulations influence the practice of individual medical doctors more than any decisions they get to make individually. Yet setting the constraints well does require coordination of efforts across individuals, especially to achieve global rather than local optima. Signaling via prices to communicate the necessary information requires markets, yet markets seldom make themselves, and nearly never make themselves perfect or complete, as emphasized by~\cite{stiglitz-walsh}. The constraints on optimization or on more general dynamics tend to be more influential than any quantity being optimized. It is essential that the boundaries we set for ourselves be fair, even if that requires the boundaries to be exquisitely elaborate.

\section{Multiple decision-making agents}
\label{multiple}

Sections~\ref{pareto} and~\ref{james-stein} highlight the complexities of collecting together multiple decision-making agents, as in societies. Section~\ref{pareto} discusses how efficiency is nice but not the whole story. Section~\ref{james-stein} reviews a fundamental drawback of combining multiple criteria into a single scalar objective value. These sections elaborate on the dynamical properties discussed in Sections~\ref{dynamicals} and~\ref{beyond} above, focusing on the complexities of systems with multiple interacting optimizers. Sections~\ref{pareto} and~\ref{james-stein} are more technical than the rest of the memo and mainly target readers trained in economics, game theory, and statistics (or econometrics).

\subsection{Non-uniqueness of Pareto optima}
\label{pareto}
A ``Pareto optimum'' is an equilibrium state of the world for which there is no way without going against someone else's wont that anyone would change on his or her own volition. If everyone is trying to do better for himself or herself (whatever ``better'' is supposed to mean), then a Pareto optimum is when no one can do better without making someone else do worse. While Pareto optima can be preferable to other equilibria (and appropriate exchanges and trades may in principle move the world to such optima), they are not unique. In the technical terms used by economists when discussing ``Edgeworth boxes,'' choosing among the points along the Pareto frontier answers the question of ``equity'' or ``fairness,'' which is exactly the question at hand. Suffice to say that opting for Pareto optima is an incomplete solution; for more information, the discussion of~\cite{stiglitz-walsh} goes into far greater detail than possible here. And further complicating matters is the existence of one of the authors of this memo, as his purpose in life is to make everyone worse off.

\subsection{James-Stein shrinkage}
\label{james-stein}
Combining everyone and everything into a single intelligible scalar objective is inherently problematic. Such combinations immediately encounter mathematical problems even in the simplest of scenarios. For example, a classic result of~\cite{james-stein} (based on earlier work of Charles Stein) provides an estimator of the means for three or more independent unit-variance normal distributions from given independent and identically distributed samples, and the expected squared Euclidean distance of these estimates from the correct means is strictly less than the expected squared Euclidean distance of the canonical estimates from the correct means (the canonical estimates are the empirical means, each estimated independently of the means for the other independent normal distributions) --- uniformly no matter what the correct means happen to be. Thus, even though the normal distributions are independent, as are the samples from these distributions, the performance of an estimator of their means improves (no matter what the means happen to be) by making the estimate of each mean depend on the others \dots\,provided that ``performance'' is measured via a single scalar objective value, the expected value of the square of the Euclidean distance of the estimated means from their actual values. While the expected squared Euclidean distance of the estimated means from their actual values has got to be the most natural single number describing the performance of the estimates, optimizing this single scalar value leads to the bizarre consequence that combining totally independent data improves the estimates (when measuring the improvement via the single scalar objective value). The issue is obvious: combining independent errors into a single scalar in order to define optimality can reward combining independent statistics that have nothing to do with each other. One scalar is not enough.

\section{A real individual goes beyond optimizing a scalar}
\label{reality}

Sections~\ref{paradoxes} and~\ref{irrationalutilities} discuss actual human behavior, in the form of Allais' Paradox (in Section~\ref{allais}) and Ellsberg's Paradox (in Section~\ref{ellsberg}), as well as in terms of irrational behavior (with psychology discussed in Section~\ref{irrational}, the Utility Theorem of Von Neumann and Morgenstern discussed in Section~\ref{von-neumann-morgenstern}, and the inadequacy of reinforcement learning discussed in Section~\ref{reinforcement}). Thus, beyond the impediments to joint, global optimization discussed in Section~\ref{multiple} that are inherent to any complicated multi-agent system, in reality even the individual agents deviate from classical economists' ideals of optimizers. The presentation below follows economists' convention of distinguishing between quantifiable ``risk'' and unquantifiable ``uncertainty.''

\subsection{Two paradoxes}
\label{paradoxes}

\subsubsection{Maurice Allais' Paradox (uncertainty of risk)}
\label{allais}
For reasons of both tractability and the limitations of human reasoning, many decisions are made with somewhat fuzzy numbers, rather than strictly targeting a single well-defined precise scalar objective value. This is only natural, as illustrated by the following modernized ``paradox'' of~\cite{allais}:

Consider two separate choices, each between two gambles.

In one of the decisions (a), you must choose between getting \$1 billion for certain, or getting \$1 billion 89\% of the time, \$2 billion 10\% of the time, and nothing 1\% of the time.

In the other decision (b), you must choose between getting \$1 billion 11\% of the time (and nothing 89\% of the time), or getting \$2 billion 10\% of the time (and nothing 90\% of the time).

Almost everyone chooses getting \$1 billion for certain and getting \$2 billion 10\% of the time. Yet, if an individual has (finite) values $v_0$ for getting nothing, $v_1$ for getting \$1 billion, and $v_2$ for getting \$2 billion, then nearly everyone goes with (a) $v_1 > .89 v_1 + .10 v_2 + .01 v_0$ and (b) $.11 v_1 + .89 v_0 < .10 v_2 + .90 v_0$. But, inequality (a) is equivalent to $.11 v_1 > .10 v_2 + .01 v_0$ whereas inequality (b) is equivalent to $.11 v_1 < .10 v_2 + .01 v_0$, and hence the inequalities are contradictory. Perhaps most people round 89\% to 90\% and round 11\% to 10\% for decision (b); most people would not round the 1\% chance of nothing in decision (a) down to 0\% chance, of course. Do most people often have to make decisions in which the difference between an estimate of 89\% and an estimate of 90\% is statistically significant? If so, then they would have to be calculating very carefully! In the design of algorithms, overestimating people's adherence to certain ideals would not be really fair.

\subsubsection{Daniel Ellsberg's Paradox (uncertainty of uncertainty)}
\label{ellsberg}
Doing best according to a given model is hard enough for most; finding the best model is even harder, and in practice much is so completely unknown as to be unquantifiable. Real decision makers take this into account, as illustrated by the following modernized ``paradox'' of~\cite{ellsberg}:

Consider two separate choices, each between two gambles.

In one of the decisions ($\alpha$), you must choose between getting \$1 billion 95\% of the time or \$1 billion ($90+x$)\% of the time, where $x$ is some unspecified whole number between 0 and 10.

In the other decision ($\beta$) to be made, you must choose between getting \$1 billion 95\% of the time or \$1 billion ($100-x$)\% of the time (with the same $x$).

Flipping a fair coin determines which of the payoffs you get to take (that is, whether from ($\alpha$) or from ($\beta$)).

Many people strongly prefer to get the \$1 billion 95\% of the time for both decisions. Yet, if as proper ``Bayesian'' decision makers, we assigned a ``prior'' probability $p_x$ for each possible value of $x$, with the sum over $x = 0$, $1$, $2$, $\dots$, $10$ of $p_x$ being 1, then the expected value of the payoff when choosing both options whose success depends on $x$ would be the sum over $x = 0$, $1$, $2$, $\dots$, $10$ of $.5 (90+x)\% p_x v_1 + .5 (100-x)\% p_x v_1 = .95 v_1$, where $v_1$ is the value to the individual of winning \$1 billion. Yet $.5(95\%)v_1 + .5(95\%)v_1 = .95 v_1$ is also the expected value when choosing both options whose success is always 95\%, independent of $x$! Thus, no matter whatever fixed distribution of prior probabilities an individual could use, the proper Bayesian individual would be indifferent between the options involving and not involving the unknown $x$ (furthermore, learning the result of the flip of the fair coin would not update the Bayesian prior, as the coin has nothing to do with $x$). Many people apparently try to avoid unknown uncertainties. Why and how exactly they decide to avoid the unknown uncertainty remains an open question (do people mistrust their own reasoning in complicated scenarios?), but collapsing everything down to one precise number --- the ``expected risk'' --- is not what they do. Assuming that they do (as in much classical literature on economics and decision making) would be unfair.

\subsection{Irrationality and utilities}
\label{irrationalutilities}

\subsubsection{Irrational human psychology}
\label{irrational}
There are whole fields devoted to ``irrationality,'' including behavioral economics and many branches of cognitive and social psychology. Irrationality happens both at the level of the individual and in social phenomena such as the ``bandwagon effect,'' ``herd behavior,'' ``groupthink,'' ``cargo cults,'' and ``echo chambers.'' Recently these studies and terms have become part of popular science, too, including via works of~\citet{kahneman} and~\citet{thaler}. Related concepts include the ``bounded rationality'' and ``satisficing'' of~\cite{simon}. Whatever people do, they do not behave as perfectly rational, cold-hearted calculators, faultlessly greedily maximizing perceived utility. Around people, algorithms ought not assume too much rationality.

\subsubsection{(Non)existence of utilities in reality}
\label{von-neumann-morgenstern}
The Utility Theorem of~\cite{von_neumann-morgenstern} states that if the (counterfactually) elicited preferences of an individual satisfy four axioms (namely: completeness, transitivity, continuity, and independence of irrelevant alternatives), then there exists a scalar-valued ``utility'' function of the individual for which the individual's decision will maximize the expected value. For actual practice, few real individuals can make all the necessary numerical calculations in time for every decision in order to satisfy the axioms of the theorem (Allais' Paradox discussed in Section~\ref{allais} is a classic example of violating the independence of irrelevant alternatives). This is especially true when considering different time horizons and trying to discount utility appropriately. Moreover, unquantifiable ``uncertainty'' yields a different result than does quantifiable ``risk'' (as in Ellsberg's Paradox discussed in Section~\ref{ellsberg}), and uncertainty is greater when the time permitted for determining a preference and making a decision is limited.

Postulating the four axioms is suspect in many real-life scenarios. For instance, would someone really be ``irrational'' for preferring Princeton to Stanford, preferring Stanford to Yale, and preferring Yale to Princeton (perhaps while not being able to decide among all three simultaneously)? The preferences just mentioned violate the axiom of transitivity. Such preferences can easily arise via a ``Condorcet Paradox'': an individual may have many criteria for rating one university against another, and a majority of these criteria could prefer Princeton to Stanford, Stanford to Yale, and Yale to Princeton for each pairwise comparison (with a different majority in each comparison). Besides, in reality people do not consider counterfactually (hypothetically) every possibility, much less elicit their response to every possibility experimentally; any assumption of what would happen if they did is therefore not fully falsifiable. Furthermore, as also noted by~\cite{von_neumann-morgenstern}, people's preferences tend to change after every decision they make, complicating the measurement of ``revealed'' preferences or ``subjective'' probabilities (even if such did in fact exist).

Thus, the existence of the celebrated Utility Theorem should have little bearing on ethics or morality, as real people may not obey the theorem's assumptions.

\subsubsection{Just rewards?}
\label{reinforcement}
The lack of a good instantiation of what economists call ``utility'' (whether ``marginal'' or otherwise) precludes much real behavior from being dictated by ``value functions'' (or good incentives in the form of rewards), as in the ``reinforcement learning'' of~\cite{sutton-barto} and others \dots\,unless these are vector-valued rather than scalar-valued, not admitting a ``total'' ordering of their values. (A ``total'' ordering is a relation, conventionally denoted ``$\le$'', for which any two objects can be related: $a \le b$ or $b \le a$, for any objects $a$ and $b$, with $a = b$ if and only if $a \le b$ and $b \le a$; and for which $a \le b$ and $b \le c$ implies $a \le c$, for any objects $a$, $b$, and $c$. Collections of scalar numbers such as integers or real numbers have natural total orderings; collections of arbitrary sets of numbers rarely have natural total orderings.) A scalar value function can be only part of the whole picture.

\section{Scientism}
\label{scientism}

Optimizing objective values is also subject to more general hazards of quantitative analysis. Beware of fallible people ``adjusting'' or ``correcting'' the data and statistics. In practice, so-called ``instrumental variables'' and ``propensity scores'' are often used to fudge results according to the preconceptions, incompetence, or even self-interest of the investigator, as discussed (for both instrumental variables and propensity scores) by~\cite{luo-gardiner-bradley} and~\cite{winkelmayer-kurth}. As emphasized by~\cite{pocock-elbourne} and myriad others, such attempts to control for confounding factors are treacherous without proper randomized experiments, while randomized experimentation on actual people tends to be taboo.

Corruption and bias (whether conscious or not) plague essentially all real communities, including social, scientific, and statistical communities. The observations of~\citet{huff}, ``How to Lie with Statistics,'' tellingly highlight what is perhaps the foremost ``use'' of statistics, as does a statement attributed by~\citet{wainer-koretz} to Winston Churchill: ``\dots when I call for statistics about the rate of infant mortality, what I want is proof that fewer babies died when I was Prime Minister than when anyone else was Prime Minister. That is a `political statistic'.'' Spinning facts or figures is ubiquitous. Scientific consensus is hard to attain --- especially hard for delicate social matters subject to statistical fluctuations --- and is often suspect even when attained. Ethical systems need to be robust to bad objectives.

\section{Judicial and professional systems}
\label{judicial}

Perhaps we should move beyond optimizing a single scalar objective and instead focus on heuristics, intelligence, experience, history, and precedent? Starkly, the key to any well-functioning set of laws has always been the judiciary, which resolves the inevitable contradictions in the application of laws, via ``fair and reasonable'' ``interpretations,'' that is, making decisions beyond what the laws could specify, decisions to which all parties will accede. \cite{goodin} comprehensively reviews the history and outlook. It is impossible to specify everything in writing ahead of time, and intractable to make intelligible written prescriptions be even mildly consistent, much less optimal according to a single universal scalar objective.

Politics and law are all about checks and balancing. Balance is also key in the medical profession: a doctor cannot distill a patient's treatment into optimization of a single scalar ``health objective value'' analogous to a credit score. The doctor instead runs big batteries of tests; even a blood test reports many metrics. The doctor may treat the patient so as to move the test results into ``normal'' ranges, where ``normal'' often varies from patient to patient and from population to population and might even depend on the patient's medical history, lifestyle context, and special needs. Moreover, balance is essential --- keeping a patient's triglycerides in check may take a back seat to moving blood pressure to desirable levels, which may in turn be worth sacrificing in order to maintain reasonable levels of insulin in diabetics, for example, whereas sacrificing insulin levels to manage blood pressure and keep triglycerides in check might make more sense if the risk of stroke or cardiac arrest is high. Single-mindedly optimizing one scalar metric to the detriment of others is unacceptable, while amending a single scalar to account for all infinitely many possibilities is infeasible. The same is even more true for laws and ethics \dots\ and algorithms.

\section{Conclusion}
\label{conclusion}

To recapitulate, reconciling differences in axioms and beliefs is unnecessary so long as their consequences are mutually agreeable \dots\ which is good, as there are large differences between different people (both in their values and in their behaviors). In particular, diverse notions of fairness are all of legitimate concern; no single scalar-valued metric of morality is the be-all and end-all. People and peoples are complex dynamical systems exhibiting complicated dynamics that no feasible optimization of a scalar-valued objective function can even characterize, much less manipulate ethically. Often the dynamics and especially the constraints on those dynamics are more important than any idealized trend toward some ``eventual'' ``optimum'' (which is typically only locally ``optimal,'' at that). And, irrespective of these concerns, aggregating the objectives of independent individuals into a single scalar unavoidably introduces undesirable dependencies (as in James-Stein shrinkage from statistics). Moreover, in reality each individual fails to optimize any scalar objective value, if only since there is uncertainty in quantifiable ``risk'' and unquantifiable ``uncertainty,'' not to mention the lack of any total order for an individual's preferences and decision-making. Indeed, the whole field of behavioral economics focuses on such observed ``irrationality.'' A sophisticated algorithm interacting with people should not optimize just a scalar objective value, as if people were models of perfection in maximizing some scalar ``utility.'' On top of all that, optimizing a scalar objective value is subject to all the usual hazards of quantitative analysis, from frustrating complication to confusion to corruption to deception with statistics (whether intentional or not).

For all the reasons discussed above, the legal and political systems need to be full of potential conflicts that get resolved case by case by trusted judges --- they cannot be fully consistent, optimizing some single scalar objective. There is no good globally consistent scalar-optimizing system, at least none that people will deem acceptable. Perhaps the best we can manage is to be reactive and institute prohibitions, rather than proactively instituting permissions through consistent centralized planning and control. Predicting the evolution of the whole world and all its bad actors can be worth trying, but will probably end up being largely hopeless. The key could be to react extraordinarily fast and resolutely, solving problems immediately as they arise. In the presence of uncertainty or disagreement, setting boundaries may be more robust than trying to design and optimize objectives within the feasible set of solutions. Of course, we can try to make refinements and predictions, but should be aware of our limitations in understanding everything and foreseeing the future. Even so, artificial intelligence and data science could help identify problems that might suggest good rules to enforce. And we could presumably measure success in various ways using appropriate data analysis. Yet the world is a complicated dynamical system, a big game, that cannot optimize anything in particular, certainly not over time. Any scientific or technological apparatus must take into account both this and the hard reality of corruption and well-known psychological and sociological deficiencies. The real world is not what some believe to be ideal; good judicious morality requires more than simply trying to optimize a single scalar objective value.

\section*{Acknowledgements}
\vspace{-.5em}
We would like to thank Amos Elberg (who highlighted how the legal system is reactive, instituting prohibitions, rather than proactive, instituting permissions), Norberto Andrade, Marco Baroni, Tom Cunningham, Yevgeniy Grechka, Jon Guerin, Alex Peysakhovich, Michael Rabbat, and Larry Zitnick.

\bibliography{obval}
\bibliographystyle{plainnat}

\end{document}

config: arxiv


text:
\section{The Multiple Samples Approach}

\label{sec:subsampling}

Let $(\mathbb{X}, \rho)$ be a metric space of diameter at most $T/2$ and let
$\mathcal{P}(\mathbb{X})$ be the space of probability measures on $\mathbb{X}$,
such that, for any measure $\mu \in \mathcal{P}(\mathbb{X})$, its support
$\mathbb{X}_\mu$ is a compact set.
The space $\mathbb{X}_\mu$ is a natural object of interest in computational
topology. Its
persistent homology is usually approximated by the persistent homology
of the distance function to a
sample $X_N=\{x_1, \dots, x_N \} \subset \mathbb{X}_\mu$.
\cite{Fasy2013statistical} propose several methods for the construction of
confidence sets for the persistence diagram of $\mathbb{X}_\mu$, while
\cite{chazal2013optimal} establish optimal convergence rates for $d_b(
D_{\mathbb{X}_\mu}, D_{X_N} )$.

When $N$ is too large, the computation of the persistent homology of $X_N$ is
prohibitive, due to the combinatorial complexity of the computation. Our aim
is to study topological signatures of the data that can be efficiently computed
in a reasonable time. We define such quantities by repeatedly sampling $m$
points of $\mathbb{X}$ according to $\mu$.

For any positive integer $m$, let  $X = \{ x_1,\cdots , x_m \}
\subset \mathbb{X}$ be a sample of $m$ points from the measure $\mu \in
\mathcal{P}(\mathbb{X})$.
The corresponding persistence landscape is $\lambda_X$
and we denote by $\Psi_\mu^{m}$ the measure induced by $\mu^{\otimes
m}$ on $\mathcal{L_T}$.
Note that the persistence landscape $\lambda_X$  can
be seen as a single draw from the measure $\Psi_\mu^{m}$.
We consider the point-wise expectations of the (random) persistence landscape
under this
measure:
$\mathbb{E}_{\Psi_\mu^{m}}[\lambda_{X}(t)], t \in [0,T]$.
This quantity is relevant from a topological point of view, because
it is stable under perturbation of the underlying
measure $\mu$.
This stability result is the main result of the paper, presented
in detail in the next section.

The average landscape $\mathbb{E}_{\Psi_\mu^{m}}[\lambda_{X}]$ has a natural
empirical counterpart, which can be used as
its unbiased estimator. Let $S_1^m, \dots, S_n^m$ be $n$ independent samples of
size $m$ from $\mu$. We define the empirical average landscape as
\begin{equation}
\label{eq:avLand}
\overline{\lambda_n^m}(t)= \frac{1}{n} \sum_{i=1}^n \lambda_{S_i^m}(t), \quad
\text{ for all } t \in [0,T],
\end{equation}
and propose to  use
$\overline{\lambda_n^m}$ to estimate $\lambda_{{\mathbb{X}_\mu}}$.
The variance of this estimator under the $\ell_\infty$-distance was studied in
detail in \cite{chazal2013stochastic}. Here instead we are concerned with the
quantity  $\Vert
\lambda_{\mathbb{X}_\mu} -
\mathbb{E}_{\Psi_\mu^{m}}[\lambda_{X}] \Vert_{\infty}$, which can be seen as the
bias component (see Section \ref{sec:risk}).

In addition to the average,
we also consider using the \textit{closest sample} to
$\mathbb{X}_\mu$ in Hausdorff distance.
The closest sample method consists in choosing a sample of $m$ points of
$\mathbb{X}$, as close as possible to $\mathbb{X}_\mu$, and then use this sample
to build a landscape that approximates $\lambda_{{\mathbb{X}_\mu}}$.
Let $S_1^m, \dots, S_n^m$ be $n$ independent samples of size $m$ from
$\mu^{\otimes
m}$.
The closest sample is
\begin{equation}
\label{eq:closestSample}
\hat{C^m_n}= \arg\min_{S \in \{S_1^m, \dots, S_n^m\}} H(S, X_\mu)
\end{equation}
and the corresponding landscape function is
$\hat{\lambda_n^m} = \lambda_{{\hat{C^m_n}}}. $
Of course, the method requires the support of $\mu$ to be a known quantity.

\begin{remark}
Computing the persistent
homology of $X_N$ is $O(\exp(N))$, whereas computing
the average landscape is $O(n \exp(m))$ and the
persistent homology of the closest sample is $O(n m N + \exp(m) )$.
\end{remark}

\begin{remark}
The general framework described above is valid for the case in which
$\mu$ is a discrete measure with support $\mathbb{X}_\mu=\{x_1, \dots, x_N \}
\subset \mathbb{R}^D $.
For example, the following situation is very common in practice.  Let
$X_N=\{x_1, \dots, x_N\}$ be a given point cloud, for large but fixed $N \in
\mathbb{R}$. When $N$ is large, the computation of the persistent homology of
$X_N$ is unfeasible. Instead, we consider the discrete uniform measure $\mu$ that puts mass $1/N$ on each point of
$X_N$, and we propose to
estimate $\lambda_{{X_N}}=\lambda_{\mathbb{X}_u}$ by repeatedly subsampling $m \ll N$ points of $X_N$
according to $\mu$.
\end{remark}

We will study the
$\ell_\infty$-risk of the proposed estimators, $\mathbb{E}\left[ \Vert
\lambda_{\mathbb{X}_\mu} - \overline{\lambda_n^m} \Vert_{\infty} \right]$ and
$\mathbb{E}\left[ \Vert \lambda_{\mathbb{X}_\mu} - \hat{\lambda_n^m}
\Vert_{\infty} \right]$, under the following assumption on the underlying
measure $\mu$, which we will refer to as the {\it  $(a,b, r_0)$-standard
assumption}: there exist positive constants $a$, $b$ and $r_0 \geq 0$ such
that
\begin{equation}
\label{eq:ab}
\forall r>r_0 , \, \forall  x \in \mathbb{X}_\mu\ ,  \  \mu(B(x,r)) \geq 1\wedge
 a  r^b .
\end{equation}
For $r_0=0$, this is known as the $(a,b)$-standard assumption and has been
widely used in the literature of set estimation under Hausdorff distance
\citep{cuevas2004boundary,Cuevas09, singh2009adaptive} and more recently in the
statistical analysis of persistence diagrams \citep{chazal2013optimal,
Fasy2013statistical}.
We use the generalized version with $r_0 > 0$ to take into account the case in
which $\mu$ is a discrete measure (in which case $r_0$ depends on $N$); see Appendix \ref{sec:abtrunc} for more
details.