TITLE: $L^2$-lower semicontinuity of an integral operator on $G(x,\nabla w(x))$
QUESTION [3 upvotes]: In the paper "A posteriori error estimates for variable time-step discretizations of nonlinear evolution equations" by Nochetto, Savaré, Verdi
we find the following claim in Example 2.4:

Let $\mathcal H:=L^2(\Omega),\ p>1$
  $$ \phi(w):=\int_\Omega G(x,\nabla w(x))dx,\quad D(\phi):=L^2(\Omega)\cap W_0^{1,p}(\Omega)$$
  If $G(x,\xi):\Omega\times\mathbb R^d\rightarrow\mathbb R$ is a Carathéodory function convex and continuously differentiable in $\xi$ for a.e. $x\in\Omega$ such that
  $$ G(x,\xi)\geqslant\alpha_0|\xi|^p-\alpha_1,\quad|\nabla_\xi G(x,\xi)|\leqslant\alpha_2 (1+|\xi|^{p-1}), \quad\forall\xi\in\mathbb R^m,a.e. x\in\Omega$$
  with some positive constants $\alpha_i$, then $\phi$ is convex and lower semicontinuous in $\mathcal H=L^2(\Omega)$.

Note that l.s.c. is stated in $L^2$. (At least for $p=2$) I am interested in

either a reference to such a result with proof or a hint of how to prove this. I have dificulties to relate this to classical results like the theorem of Serrin and generalizations as they yield
$${\lim \inf}_{n\rightarrow\infty} \phi(u_n)\geqslant\phi(u)$$
only for sequences $u_n\rightarrow u$ wrt the $L^1$ norm where the $u_n$ and $u$ are in $W^{1,1}(\Omega)$ while assumptions are usually weaker.
whether or not such a result carries over to the vector-valued case, i.e. $\mathcal H=L^2(\Omega,\mathbb R^N)$.

NB: I'm a numerics guy with little practice in analysis...

REPLY [3 votes]: Ad 1: I will give a possible idea of a proof. Take a sequence $w_k \to w$ in $L^2(\Omega)$. If $\liminf\phi(w_k) = +\infty$, we are fine. Otherwise take a bounded subsequence (still denoted by $w_k$). Now you have
$$C \ge \phi(w_k) \ge \alpha_0 \int_\Omega \lvert \nabla w_k \rvert dx - \alpha_1 \, \int_\Omega dx.$$
Hence, $w_k$ is bounded in $W^{1,p}(\Omega)$ and you can select a weakly convergent subsequence (converging still towards $w$). Finally, you obtain the lower semicontinuity, since $G$ is convex in $\xi$ (use: convex + continuous gives weakly lower semicontinuous).
Ad 2: Along this lines, one should do similar things for the vector valued case.


TITLE: Minimal rank of a matrix with zero diagonal and nonzero off-diagonal entries over a finite field
QUESTION [2 upvotes]: What is the minimal possible rank of a square matrix, that:

is $m\times m$,
has elements from a finite field with $n$ elements,
has $0$s on its diagonal, and
has nonzero off-diagonal entries?

REPLY [1 votes]: The identity matrix will have maximal rank $m$.


TITLE: P vs. NP and Pseudorandom Bit Generators
QUESTION [7 upvotes]: According to an article on pseudorandom number generators (PRNG) by Jeff Lagarias, he states that trying to prove that a PRNG is unpredictable (secure) is just "as hard" as trying to prove that P!=NP. If it is considered impossible to prove mathematically that some bit sequence is random then it should be mathematically impossible to prove P!=NP, right? Are these two problems really equivalent? If they are then why all the hoopla over P vs NP, you can never prove it either way according to these definitions.

REPLY [10 votes]: Every cryptographically-secure pseudo-random bit generator $G$ is a one-way function; since given the output $y$ of $G(\cdot)$ on some input (seed) $s$, it is computationally infeasible to obtain $s$ from $y$. (Otherwise, the generator is not cryptographically-secure). So we have:
cryptographically-secure pseudo-random bit generator exists $\Rightarrow$ one-way functions exist.
The existence of one-way functions is a stronger assumption than $\rm{P}\ne\rm{NP}$. That is:
one-way functions exist $\Rightarrow$ $\rm{P}\ne\rm{NP}$.
(For more info on this, see the Status of Impagliazzo's Worlds.)

Edit:
Impagliazzo, Levin, and Luby showed that the reverse holds under non-uniform assumptions; that is:
one-way functions exist $\Rightarrow$ cryptographically-secure pseudo-random bit generator exists.
(here, the security is with reference to non-uniform adversaries.)
Håstad generalized this to uniform adversaries.
Joining forces, Håstad, Impagliazzo, Levin, and Luby showed that:
cryptographically-secure pseudo-random bit generator exists if and only if one-way functions exist.


TITLE: Question on example 3.0.1 in Yurinsky's book "Sums and Gaussian vectors"
QUESTION [3 upvotes]: Good day to All.
Let $S_{1,n} = \sum_{i=1}^{n}\xi_{i}$, where $(\xi_{i})_{i \in \mathbb{N}}$ be independent RV with values in some Banach space.
On pages 79-80 in this book author provides an example that illustrates the fact that in the infinite dimensional spaces it may be not enough to have assumptions on the distribution of the individual summands $\xi_{i}$ in order to control the deviations of $\lVert {S_{1,n}}\rVert $, where $\lVert \cdot \rVert $ is the norm of corresponding Banach space.
Author says:"In infinite dimensions, "individual" conditions may not suffice: it is sometimes necessary to include restrictions on the distribution of the sum in order to obtain stronger bounds for its "tails".The following example serves to show the relative independence of restrictions on concentration of the sum and those concerning the distributions of individual summands ".
In his example 3.0.1 let the space $c_0$ (with the norm $\|x\|_{\infty} = \sup_{n \in \mathbb{N}} |x^{(n)}|$) be the space of real-valued convergent to zero sequences and we consider an array of i.i.d. real-valued $\xi_{j}^{i} = \frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_{1}$.
Consider the sequence $\xi_{j} = ( \frac{\xi_{j}^{(i)}}{\ln\ln(10 i)}, i \in \mathbb{N} )$ which is centered, in $c_{0}$ and a.s. bounded, i.e. $\|\xi_j\|_{\infty} = \frac{1}{\ln \ln 10}$. Consider RV's $\eta_{n}^{(i)} = \sum_{j=1}^{n}\xi_{j}^{(i)}$ and notice that they are independent. One easily sees that $\mathbb{P}(\eta_{n}^{i}=n) = 2^{-n}$ and therefore it implies:
\begin{align*}
\mathbb{P}(\max_{i \leq 2^n}\eta_{n}^{(i)}<n) = \prod_{k=1}^{2^n}(1-\mathbb{P}(\eta_{n}^{(i)}=n)) \leq \exp({-2^{n} 2^{-n})} = e^{-1},
\end{align*}
where we used classical $1-x \leq \exp(-x)$ for $x\geq 0$. Thefore, for all $n$ we have:
\begin{align*}
P\left(\|S_{1,n}\|_{\infty} \geq \frac{n}{\ln \ln (10 * 2^n)}\right) \geq P\left(\max_{i \leq 2^n}\eta_{n}^{(i)} \geq n\right) \geq 1-e^{-1}.
\end{align*}
Thus, the norm of sum scales (with constant probability separated from zero) like $\frac{n}{\ln (n)}$, even though its coordinates have variance of order $\sqrt{n}$.
I don't really understand why author gives the final remark about the variance of the coordinates, although (as it seemed to me, maybe I am wrong) the qoal was to show that even though we have for each $i \leq n$, $\|\xi_{i}\|_{\infty} \leq 1$ a.s., the typical deviations of $\|S_{1,n}\|_{\infty}$ is of order $n/\ln(n)$ (and not for example $\sqrt{n}$ as it would be in some Hilbert space).
Also my question: can't we also consider $l^{\infty} := \{x=(x^{(n)}) : \sup_{n\in \mathbb N}| x^{(n)}| \lt \infty\}$ (which is Banach space with respect to the norm  $\|x\|_{\infty} = \sup_{n \in \mathbb N} |x^{(n)}|$) and just the sequences $\xi_{j} = (\xi_{j}^{j}, j \in \mathbb{N})$ (without additional log weight ) and $\xi_{j}^{i} = \frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_{1}$ i.i.d in $i,j$ as in example 3.0.1? Then, it seems the same reasoning as in the book applies for this case.

REPLY [2 votes]: Yes we can. Indeed, with $\xi_j= (\xi_j^i)_{i=1}^\infty$ and $\eta_n=(\eta_n^i)_{i=1}^\infty:=\sum_1^n\xi_j$, we see that $\eta_n^1,\eta_n^2,\dots$ are iid random variables with values in $[-n,n]$ and $P(\eta_n^1=n)=1/2^n>0$. Hence,
$$\|\eta_n\|_\infty=\sup_{i=1,2,\dots}|\eta_n^i|=n
$$
almost surely, whereas $\|\xi_j\|_\infty=1$.

I guess Yurinsky used $c_0$ rather than $\ell^\infty$ because he wanted the Banach space to be separable (which is convenient to avoid certain measurability questions). Perhaps, the separability condition is assumed throughout the Yurinsky book. However, in our "discrete" setting, we don't have to worry about measurability.


TITLE: Factoring $x^3-8$ by grouping
QUESTION [0 upvotes]: I'm trying to factor by grouping. It worked for me with polynomial division, but I can't get it to work by grouping.
$$x^3-8$$
The answer should be $(x−2)(x^2+2x+4)$.

So first, the groups are:
$$(x^3 + 0x^2) + (0x - 8)$$
Take the factors out:
$$x^2(x + 0) + 1(0x - 8)$$
Then:
$$(x^2 + 1) + (x + 0) + (0x - 8)$$
So:
$$x^2+x-7$$
It is clearly wrong by now. But what did I miss?

REPLY [0 votes]: If you know that you will have an $(x - 2)$ factor (which you can see by setting $(x^3 - 8)$ equal to $0$ and solving $x^3 = 8$ for the simple real solution $x = 2$), then let's work toward isolating the $(x - 2)$:
$$x^3 - 8$$
Here I know that I will want to end up with $(x^2)(x - 2) + ...$, so I know I will have a $-2x^2$ component. Then, since I will need a $+2x^2$ component to cancel that, I know that I will want to have a $(2x)(x - 2) + ...$, so I will need a $+4x$ component to cancel the $-4x$:
$$x^3 + (-2x^2 + 2x^2) + (-4x + 4x) - 8$$
Associating:
$$(x^3 + -2x^2) + (2x^2 + -4x) + (4x - 8)$$
Rewriting to clarify $(foo + -bar)$:
$$(x^3 - 2x^2) + (2x^2 - 4x) + (4x - 8)$$
Factoring:
$$(x^2)(x - 2) + (2x)(x - 2) + 4(x - 2)$$
Un-distributing:
$$(x^2 + 2x + 4)(x - 2)$$
Commuting:
$$(x - 2)(x^2 + 2x + 4)$$