TITLE: Find $\max(PA-PB)$ where $A(1,3)$ and $B(5,2)$
QUESTION [0 upvotes]: If $P$ lies on the line $y=x$ find $\max(PA-PB)$ where $A(1,3);B(5,2)$

By drawing a rough sketch we see that $A$ and $B$ lie on opposite sides of $P$(Actually the line $y=x$).
I tried using triangle inequality that $PA-PB\leq AB$ where equality holding when the triangle in degenerate.But I am not satisfied that this claim holds when $P$ lies between $A$ and $B$.[By the way I am satisfied that this claim is true when $P$ didives the line $AB$ externally].Is this claim correct even when $P$ divides $AB$ internally?Does max hold when $A,B,C$ are collinear?
How to solve this?

REPLY [1 votes]: To make things easier we rotate the picture so $AB$ is on the x-axis with the midpoint as origin, and $P$ lies on $y=\frac53 x$. (by tangent addition formula)
Since a hyperbola is the locus of points which have the value $PA-PB$ fixed, we want to find the hyperbola of maximum constant value ($2a$) with axis $AB$ and intersecting $y=\frac53 x$.
According to the article, a hyperbola centered at the origin has asymptotes with slopes $\pm \frac ba$, where $b=\sqrt{c^2-a^2}$, $c$ being half the length of $AB$ ($c=\frac{\sqrt{17}}2$, so $\frac ba=\sqrt{\frac{17}{4a^2}-1}$). Since the hyperbola intersects $y=\frac53x$ iff the slope of its asymptote is $>\frac53$, we want to find the maximum value of $a$ such that $\sqrt{\frac{17}{4a^2}-1}>\frac53 \implies a<\frac3{2\sqrt2}$.
Since $PA-PB=2a$, in this case we have $\sup(PA-PB)=\frac3{\sqrt2}$, although the maximum is only achieved at the point at infinity.


TITLE: The names of 8 students are listed randomly. What is the probability that Al, Bob, and Charlie are all in the top 4?
QUESTION [1 upvotes]: My attempt at a solution: There are $C_{4,3}$ ways to arrange Al, Bob, and Charlie in the top 4, and $C_{5,4}$ ways to arrange the other 5 people. All of this is over $C_{8,4}$, giving $$\frac{C_{4,3}C_{5,4}}{C_{8,4}}=\frac{2}{7}$$ Is this correct?

REPLY [1 votes]: $4$ slots are up for grabs, so a simple way is to just  compute $\dfrac48\cdot\dfrac37\cdot\dfrac26= \dfrac{1}{14}$


TITLE: If $\|x_n\|_2 \to \infty$ in $L_2$-norm, does $\|x_n\|_{1+\varepsilon} \to \infty$ in $L_{1+\varepsilon}$-norm, for all $\varepsilon > 0$?
QUESTION [2 upvotes]: Question: If $\|x_n\|_2 \to \infty$ in $L_2$-norm, does $\|x_n\|_{1+\varepsilon} \to \infty$ in $L_{1+\varepsilon}$-norm, for all $\varepsilon > 0$?
Details/Progress: This should follow trivially for $\varepsilon \geq 1$ because $\|x\|_p \leq \|x\|_{q}$ for any $1\leq p \leq q < \infty$, but I am wondering if I can show it also holds for $\varepsilon \in (0,1)$. This clearly does not hold in general, but I have more information for the case at hand: Specifically, I am considering sequences $x_n$ in the space of square-integrable probability densities, i.e.
$$
 C = \{x \in L_2(\mathbb{R^n}) | x \geq 0 \text{ and} \int_{\mathbb{R}^n}x(z)dz = 1 \}.
$$
Intuitively, I think that because one can only allocate a total area under the curve of size $1$, any sequence $x_n$ in this space that diverges to $\infty$ needs to have some neighbourhood on which $x_n(z)$ grows larger and larger (so that the divergence of $\int_{\mathbb{R}^n}x(z)^{2}dz$ happens purely on that neighbourhood). This makes me think that on that same neighbourhood, $\int_{\mathbb{R}^n}x(z)^{1+\varepsilon}dz$ should also diverge. Is this intuition correct? If so, is there an appropriate/easy way to formalize it? If not, do you know of a counterexample?

REPLY [2 votes]: Consider $f(z)=\frac{1}{4\sqrt{\vert z \vert}} \chi_{[-1;1]}(z)$. Now define
$$ a_n =\int_{[-1/n;1/n]} f(z) dz $$
and define
$$ x_n(z) = f(z)\chi_{[-1;1]\setminus{ [-1/n; 1/n]}}(z) + a_n\chi_{[2;3]} $$
Then we have $x_n \in C$. By monotone convergence we get that the $L^2$ norm of $(x_n)$ explodes. However, as $f\in L^{1+\varepsilon}$ for $0<\varepsilon <1$ we get by dominated convergences that the $L^{1+\varepsilon} $ norm stays bounded (in fact it converges to $\Vert f\Vert_{L^{1+\varepsilon}}$).


text:
\section{Proof of Theorem~\ref{thm:main}}
\label{sec:proofs-of-the-theorem}

Let $G$ be a graph, $S$ be a set of vertices in \(G\), and let \(d\) be a positive integer.
For a vertex $u$ in $G$, the \emph{distance-$d$ profile} of $u$ on $S$ in $G$ is defined as a function $\profile^d_G[u, S]$ from $S$ to $\set{0, \dots, d, \infty}$ given by
\[
\profile^d_G[u, S](x) =
\begin{cases}
  \dist_G(u, x) &\text{if $\dist_G(u, x) \leq d$,}\\
  \infty &\text{otherwise.}
\end{cases}
\]
The \emph{distance-$d$ profile complexity} of $S$ in $G$ is the number of different distance-$d$ profiles on $S$ in~$G$.
We will use the following result of Eickmeyer et al.~\cite{EickmeyerGKKPRS17}.

\begin{theorem}[\cite{EickmeyerGKKPRS17}]\label{thm:distance-profile-complexity}
  Let $\calC$ be a nowhere dense class of graphs, \(d\) be a positive integer,
  and $\epsi$ be a positive real.
  Then there is an integer \(m_0\)
  such that
  for every graph $G$ in $\calC$ and every subset $S$ of $V(G)$ with \(|S| \ge m_0\),
  the distance-\(d\) profile complexity of \(S\) in $G$ is at most $|S|^{1+\epsi}$.
\end{theorem}

With all the tools prepared, we may proceed to the proof of our main result.

\begin{proof}[Proof of Theorem \ref{thm:main}]
  It is enough to prove the theorem for sufficiently small \(\epsi\), so
  we assume that \(\epsi < 1\).
  Let \(\epsi' = \epsi / 3\).
  Let \(k_0'\) be the integer obtained by
  applying Lemma~\ref{lem:new-abs} to \(\calC\), \(d\), and \(\epsi'\).
  Let \(m_0\) be the integer obtained by applying Theorem~\ref{thm:distance-profile-complexity}
  to \(\calC\), \(d\) and \(\epsi=1\), so that the distance-\(d\) profile complexity of
  any \(m\)-element vertex subset in a graph from \(\calC\) is at most \(m^2\), provided \(m \ge m_0\).
  We prove the theorem for \(k_0\) defined as
  \[k_0 = \max \left\{k_0', \ceil*{(m_0 + 1)^{1/\epsi'}}\right\}.\]

  Let \(G\) be a graph in \(\calC\) and
  let \(A\) and \(B\) be two nonempty sets of vertices in \(G\) satisfying \(|A \cup B| \geq k_0\).
  Let \(k=|A \cup B|\).
  Since \(k\geq k_0 \ge k_0'\),
  there exist disjoint subsets \(A_0\) and \(B_0\)
  of \(A\) and \(B\) respectively,
  and there is a vertex subset \(S\) in \(G\) such
  that \(|A_0| \ge (1-\epsi')|A| \ge (1-\epsi)|A|\), \(|B_0| \ge |B|/k^{\epsi'}\),
  \(|S| \le k^{\epsi'}\), and every \(A_0\)--\(B_0\)-path of length at most
  \(d\) in \(G\) intersects \(S\).
  By adding arbitrary vertices of $G$ if necessary, we may assume that
  $k^{\epsi'}\geq |S| > k^{\epsi'}-1$. This is possible since $\epsi'\le 1$ and $|V(G)|\geq |A\cup B|= k$.
  Therefore,
  \[
  k^{\epsi'} \geq |S| > k^{\epsi'}-1 \ge k_0^{\epsi'}-1 \ge (m_0 + 1) - 1 = m_0.
  \]
  We infer that the distance-$d$ profile complexity of \(S\) in \(G\) is at most \(|S|^2\).
  Therefore, there is a subset \(B'\) of

  \(B_0\) in which all vertices have the same distance-\(d\) profile on \(S\)
  and
  \[
  |B'| \ge |B_0|/|S|^2 \geq |B_0|/k^{2\epsi'} \ge |B|/k^{3\epsi'} = |B|/k^{\epsi}.
  \]

  To prove that the sets \(A_0\) and \(B'\) satisfy the theorem, it suffices to
  show that all elements of \(B'\) have the same distance-\(d\) profile on \(A_0\),
  that is for any \(a \in A_0\) and
  \(b_1, b_2 \in B'\),  if \(\dist_G(b_1, a) \le d\) then
  \(\dist_G(b_2, a) = \dist_G(b_1, a)\).
  Suppose then, that \(\dist_G(b_1, a) \le d\).
  A shortest \(a\)--\(b_1\) path intersects
  \(S\) in a vertex \(s\) such that
  \(\dist_G(b_1, a) = \dist_G(b_1, s) + \dist_G(s, a)\).
  Since \(\profile^d_G[b_1, S] = \profile^d_G[b_2, S]\),
  we have
  \[\dist_G(b_2, a) \le \dist_G(b_2, s) + \dist_G(s, a) =
  \dist_G(b_1, s) + \dist_G(s, a) = \dist_G(b_1,a) \le d.\]
  A symmetric argument shows that \(\dist_G(a, b_1) \le \dist_G(a, b_2)\), so
  indeed \(\dist_G(a, b_1) = \dist_G(a, b_2)\).
  This completes the proof of the theorem.
\end{proof}

config: arxiv


TITLE: Divisor summatory function for Odd and Even numbers
QUESTION [1 upvotes]: With Dirichlet's Divisor summatory function the mean divisor growth can be determined.
$$D(x)=\frac{1}{x} \sum_{n=1}^x d(x)= \log(x)+2 \gamma -1+ \mathcal{O}\!\left(\frac{1}{\sqrt{x}}\right)$$
Where $\gamma$ is the Euler's constant and $d(n)$ is the divisor function. Do there exist expressions where the Divisor summatory function is expressed in: $D(x=odd)$ and $D(x=even)$?
Background for question error growth "Wave Divisor Function":
Error in Divisor Function Modelled With Waves

REPLY [2 votes]: Not sure if that's the question but if one wants the expressions for $d_{odd}(x)=\sum_{2k+1 \le x}d(2k+1)$ and $d_{even}$, one can easily get them from the recurrence:
$d_{even}(x)=2d_r(x/2)-d_r(x/4), d_{odd}(x)=d_r(x)-2d_r(x/2)+d_r(x/4)$ where $d_r(x)=xD(x)$ the usual divisor sum - these follow from the relation $d(4q)=2d(2q)-d(q)$ for any integer $q \ge 1$
In particular one gets that $D_{odd}=\frac{1}{4}\log x+\frac{1}{4}(2\gamma -1 + \log 4)+ O(1/\sqrt x)$ and $D_{even}=\frac{3}{4}\log x+\frac{3}{4}(2\gamma -1) -\frac{1}{4}\log 4+ O(1/\sqrt x)$
One can also apply Perron to get the principal terms - for the usual divisor sum it is the residue at $1$ of $\zeta^2(s)x^s/s$, while here one can immediately notice that $\zeta_{odd}(s)=(1-2^{-s})\zeta(s)$ so squaring $\zeta_{odd}(s)^2x^s=\zeta^2(s)x^s-2\zeta^2(s)(x/2)^s+\zeta^2(s)(x/4)^s$ from which the above follow easily too


text:
\section{Two Applications}
\label{sec:applications}

Graph polynomials have a wide range of applications throughout many
fields.  We have already seen some examples of this with various
applications of the classical Tutte polynomial in the previous
chapter.  Here we present two representative important applications
(out of many possible) and show how they may be modeled by graph
polynomials.

\subsection{DNA Sequencing}
\label{subsec:dna}

We begin with string reconstruction, a problem that may be modeled by
the interlace and circuit partition polynomials
\index{interlace polynomial}
\index{polynomial!interlace}
\index{circuit partition polynomial}
\index{polynomial!circuit partition} (and hence
indirectly in special cases by the Tutte polynomial).
String reconstruction is the
process of reassembling a long string of symbols from a set of its
subsequences together with some (possibly incomplete, redundant, or
corrupt) sequencing information.  While we focus on DNA sequencing,
which was original the motivation for the development of the interlace
polynomial, the methods here apply to any string reconstruction
problem. For example, fragmenting and reassembling messages is a
common network protocol, and reconstruction techniques might be
applied when the network protocol has been disrupted, yet the original
message must be reassembled from the fragments.

DNA sequences are typically too long to read at once with current laboratory techniques, so researchers
probe for shorter fragments (reads) of the strand.  They then are
faced with the difficulty of recovering the original long sequence
from the resulting set of subsequences.  DNA sequencing by
hybridization is a method of reconstructing the nucleotide sequence
from a set of short substrings (see Waterman~\cite{Wat95} for an
overview).

The problem of determining the number of possible reconstructions may
be modeled using Eulerian digraphs, with a correct sequencing of the
original strand corresponding to exactly one of the possible Eulerian
circuits in the graph.  The probability of correctly sequencing the
original strand is thus the reciprocal of the total number of Euler
circuits in the graph.

 The most basic (two-way repeats only) combinatorial model  for DNA
 sequencing by hybridization uses an Eulerian digraph with two
 incoming and two outgoing edges at each vertex (see
 Pevzner~\cite{Pev89} and Arratia, Martin, Reinert,
 Waterman~\cite{AMRW96}). The raw data consists of all subsequences of
 the DNA strand of a fixed length L, called the L-spectrum of the
 sequence.  As L increases, the statistical probability that the
 beginning and end of the DNA strand are the same approaches zero, as
 does the likelihood of three or more repeats of the same pattern of
 length L or more in the strand (see Dyer, Frieze, and
 Suen~\cite{DFS94}).  Thus, this model assumes that the only
 consideration in reconstructing the original sequence is the
 appearance of interlaced two-way repeats, that is, alternating
 patterns of length L or greater, for example, $\dots \text{ACTG}
 \dots \text{CTCT} \dots \text{ACTG} \dots \text{CTCT} \dots$ .

From the multiset (duplicates are allowed) of subsequences of length
L, create a single vertex of the de Bruijn graph for each subsequence
of length L-1 that appears in one of the subsequences.  For example,
if L = 4 and ACTG appears as a subsequence, create two vertices, one
labeled ACT and one labeled CTG.  Edges are directed from head to tail
of a subsequence, e.g. there would be a directed edge from ACT to CTG
labeled ACTG.  If there is another subsequence ACTT, we do not create
another vertex ACT, but rather draw an edge labeled ACTT from the
vertex ACT to a new vertex labeled CTT.  If, in the multiset of
subsequences, ACTG appears twice, then we draw two edges from ACT to
CTG.

The beginning and end of the strand are identified to be represented
by the same vertex, and, since by assumption no subsequence appears
more than twice, the result is an Eulerian digraph of maximum degree
4.  Tracing the original DNA sequence in this graph corresponds to an
Eulerian circuit that starts at the vertex representing the beginning
and end of the strand.  All other possible sequences that could be
(mis)reconstructed from the multiset of subsequences correspond to
other Eulerian circuits in this graph.  Thus (up to minor reductions
for long repeats and forced subsequences), finding the number of DNA
sequences possible from a given multiset of subsequences corresponds
to enumerating the Eulerian circuits in this directed
graph.

The generalized transition polynomial models this problem directly:
when the pair weights are identically 1, it reduces to the circuit
partition polynomial.  This is a generating function for families of
circuits in a graph, so the coefficient of $x$ is the number of
Eulerian circuits. The interlace polynomial informs the problem as
follows. Consider an Eulerian circuit through the de Bruijn graph,
which gives a sequence of the vertices visited in order.

Now construct the interlace graph by placing a vertex for each symbol
and an edge between symbols that are interlaced (occur in alternation)
in the sequence. The interlace polynomial of the interlace graph is
then a translation of the circuit partition polynomial of the original
de Bruijn graph, as in Theorem~\ref{A}, where again the coefficient of $x$ is the number of
Eulerian circuits (see Arratia, Bollob\'as, Coppersmith, and
Sorkin~\cite{ABCS00}, and Arratia, Bollob\'as, and
Coppersmith~\cite{ABS00, ABS04a}).

One of the original motivating goals of Arratia, Bollob\'as,
Coppersmith, and Sorkin ~\cite{ABCS00} was classifying Eulerian
digraphs with a given number of Eulerian circuits. The BEST theorem,
a formula for the number of the circuits of an Eulerian graph in terms
of its Kirchhoff matrix (see Fleischner~\cite{Fle91} for good
exposition) gives only a tautological classification: the Eulerian
digraphs with $m$ Eulerian circuits are those where BEST theorem
formula gives $m$ circuits.  Critically, all of the above graph
polynomials encode much more information than is available from the
BEST theorem, and all of them are embedded in broader algebraic
structures that provide tools for extracting information from them.
Thus, they better serve the goal of seeking structural
characterizations of graph classes with specified Eulerian circuit
properties.

\subsection{The Potts Model of Statistical Mechanics}
\label{subsec:potts}

Here we have an important physics model that remarkably was found to
be exactly equivalent to the Tutte polynomial.
 \index{Tutte polynomial}\index{polynomial!Tutte}

Complex systems are networks in which very simple interactions at the
microscale level determine the macroscale behavior of the system. The
Potts model \index{Potts model partition function} of statistical
mechanics models complex systems whose behaviors depend on nearest
neighbor energy interactions.  This model plays an important role in
the theory of phase transitions and critical phenomena, and has
applications as widely varied as magnetism, adsorption of gases on
substrates, foam behaviors, and social demographics, with important
biological examples including disease transmission, cell migration,
tissue engulfment, diffusion across a membrane, and cell sorting.

Central to the Potts model is the Hamiltonian, \index{Hamiltonian}
\[
 h(\omega ) =  - J\sum\limits_{\{ i,j\}  \in E(G)}
              {\delta (\sigma _i,\sigma _j )} \;,
\]
 a measure of the energy of the system.  Here a
spin, $\sigma _i $, at a vertex $i$, is a choice of condition (for
example, healthy, infected or necrotic for a cell represented by the
vertex). $J$ is a measure of the interaction energy between
neighboring vertices, $\omega $ is a state of a graph $G$ (that is, a
fixed choice of spin at each vertex), and $\delta $ is the Kronecker
delta function.

The Potts model partition function is the normalization factor for the
Boltzmann probability distribution.  Systems such as the Potts model,
following Boltzmann distribution laws, will have the number of states
with a given energy (Hamiltonian value) exponentially distributed.
Thus, the probability of the system being in a particular state
$\omega$ at temperature $t$ is:
\[
\Pr \left( {\omega ,\beta } \right) = \frac{{\exp \left( { - \beta
        h\left( \omega  \right)} \right)}}{{\sum {\exp \left( { -
          \beta h\left( \varpi  \right)} \right)} }}.
\]
Here, the sum is over all possible states $\varpi$ of G, and $\beta  =
\frac{1}{{\kappa t}}$
, where $\kappa  = 1.38 \times 10^{ - 23} $ joules/Kelvin is the
Boltzmann constant. The parameter $t$ is an important variable in the
model, although it may not represent physical temperature, but some
other measure of volatility relevant to the particular application
(for example ease of disease transmission/reinfection).  The
denominator of this expression, $P\left( {G;q,\beta } \right) = \sum
{\exp \left( { - \beta h\left( \varpi  \right)} \right)} $, called the
Potts model partition function, is the most critical, and difficult,
part of the model.

Remarkably, the Potts model partition function is equivalent to the
Tutte polynomial: \index{Tutte polynomial}\index{polynomial!Tutte}
\[
P\left( {G;q,\beta } \right) = q^{k\left( G \right)} v^{\left|
    {v\left( G \right)} \right| - k\left( G \right)} T\left(
  {G;\frac{{q + v}}{v},v + 1} \right),
\]
where $q$ is the number of possible spins, and $v = \exp (J\beta ) -
1$.  See Fortuin and Kasteleyn \cite{FK72} for the nascent stages of
this theory, later exposition in Tutte ~\cite{Tut84}, Biggs
~\cite{Big96}, Bollob\'as ~\cite{Bol98}, Welsh ~\cite{Wel93}, and
surveys by Welsh and Merino ~\cite{WM00}, and Beaudin, Ellis-Monaghan,
Pangborn and Shrock ~\cite{BE-MPS}.

One common extension of the Potts model involves allowing interaction
energies to depend on individual edges.  With this, the Hamiltonian
becomes $h(\omega ) = \sum_{e \in E(G)} {J_e \delta (\sigma _i
  ,\sigma _j )} $, where $J_e $  is the interaction energy on the edge
$e$.  The partition function is then
 \[
P\left( G \right) = \sum\limits_{A \subseteq E\left( G \right)}
{q^{k\left( A \right)} \prod\limits_{e \in A} {v_e } },
\]
where $v_e  = \exp \left( {\beta J_e } \right) - 1$
 Again see Fortuin and Kasteleyn ~\cite{FK72}, and more recently Sokal
 ~\cite{Sok00, Sok01b}.  As we have seen in Subsection
 \ref{subsec:param tutte}, the Tutte polynomial has also been extended
 to parametrized Tutte functions that incorporate edge weights.   The
 generalized partition function given above satisfies the relations of Theorem~\ref{ZBR}, however, and thus is a special case of a parametrized
 Tutte function.

This relationship between the Potts model partition function and the
Tutte polynomial \index{Tutte polynomial}\index{polynomial!Tutte}  has
led to a remarkable synergy between the fields, particularly for
example in the areas of computational complexity and the zeros of the
Tutte and chromatic polynomials.  For  overviews, see Welsh and
Merino ~\cite{WM00}, and Beaudin, Ellis-Monaghan, Pangborn and
Shrock~\cite{BE-MPS}.


TITLE: Prove or disprove this Big O and Theta proposition
QUESTION [0 upvotes]: It's the problem:
$$\log \left ( \Theta\! \left (\frac{n+1}{n} \right ) \right ) = O( \log n)$$
and I want to show if it's true or not and I know I should use Big O and Theta definition, but I don't know how exactly i can prove or disprove it.

REPLY [0 votes]: HINT: Just use the definition,
$$f(n)=\mathcal{O}(g(n))\iff \exists k>0, \exists n_{0}\in \mathbb{N},\forall n<n_{0}: |f(n)|\leqslant k \cdot g(n).$$
and about $\log\left(\Theta\left( \frac{n+1}{n}\right) \right)$ I suppose that you are saying $$\log \left(\Theta\left( \frac{n+1}{n}\right) \right):=f(n)$$
where $f(n)=\log(h(n))$ for some $h(n)\in \Theta\left(\frac{n+1}{n}\right)$ and then use the definition of $\Theta(\cdot)$.


TITLE: Rank of a distribution
QUESTION [0 upvotes]: I am reading about distributions in the context of differential geometry.

A distribution $S$ of dimension $r$ on a manifold $M$ is an assignment to each point $p \in M$ of an $r$-dimensional subspace $S_p$ of $T_pM$.

(1) Is this $r$ called rank of the distribution?
Further, I introduce a closed $3$-form $\alpha$ on $M$, and consider the distribution $\ker \alpha := \{X \in TM: \alpha(X,{}\cdot{},{}\cdot{}) = 0\}$. I read that if $\ker \alpha$ is of constant rank and has closed leaves, then I can consider the quotient $M/\ker \alpha$ with a structure induced by $\alpha$.
(2) I cannot really understand the last sentence above. Is the condition 'constant rank' necessary to construct the quotient $M/\ker \alpha$? What does 'closed leaves' mean?
Any help about (1) or (2) is appreciated. Thanks.

REPLY [2 votes]: 1) $r$ is the rank of the distribution.
2) constant rank is not necessary to construct the quotient $M/ker\alpha$. Consider $(x^2+y^2+z^2)dx\wedge dy\wedge dz$ defined on $\mathbb{R}^3$, its does not have a constant rank but its leaves are points, so the quotient space $\mathbb{R}^3/\ker\alpha$ exists.
More generally, regular foliation are studied. In this case this means that the rank of the distribution is constant and it is integrable i.e there exists submanifolds tangent to the distribution called the leaves of the foliation. This follows here from the Frobenius theorem. We also need the fact that the leaves are closed. The typical example here will be torus on which you define a foliation by irrational lines (the quotient space does not exists as a manifold are least) or a foliation by circles for which the quotient space exists.


TITLE: Is it possible to determine the impulse given to a coin during a coin flip?
QUESTION [0 upvotes]: Given that we assume the force acting on a coin as well as the distance the which force acts on the coin is constant, would it be possible to determine the linear impulse on the coin with only that information?

REPLY [0 votes]: We can calculate the angular Impulse.. (analogous to Torque and Force, Angular Impulse and Impulse)..
If we consider a simple case in which we neglect Upward motion of coin.. we cal calculate the angular velocity
J = P X R
Here, J = m∆v*r


TITLE: Density in a topological space.
QUESTION [2 upvotes]: I have the set $X=\{a,b,c,d,e\}$ with topology $T=\{\emptyset, \{a\}, \{a,b\}, \{a,c,d\},\{a,b,c,d\}, \{a,b,e\}, X\}$
I want to identify the dense subsets of $X$.
Now, I haven't worked too much with density or limit points, so I sometimes get confused when I have to juggle all the different definitions while doing the problem. So in order to ascertain that I understand these concepts, I'm just going to show my attempt to find one dense subset.
First I note that every point in $X$ different from $a$ is a limit point of $\{a\}$. Then, by the definition of a dense subset, every point in $X$ is either in $\{a\}$ or a limit point of $\{a\}$ which makes it dense in $X$. Correct reasoning or not?

REPLY [1 votes]: Def'n: Any $Y\subset X$ is dense in $X$ iff it has non-empty intersection with every non-empty open subset of $X,$ that is, with every non-empty member of $T.$
Since $\{a\}\in T,$ any dense $Y\subset X$ must necessarily satisfy $Y\cap \{a\} \ne \phi,$ that is, $a\in Y.$ But since every non-empty member of $T$ contains $a,$ it is sufficient that $a\in Y\subset X$ in order that $Y$  be dense in $X.$
So the dense subsets of $X$ are just those that contain $a.$
Assuming that $a,b,c,d,e$ are $5$ different objects, your comment that every set is dense is incorrect. For example $\{b\}$ is not dense. Although every non-empty member of $T$ is dense. But also, for example, $\{a,e\}$ is dense and does not belong to $T.$


TITLE: About localization and integral closure
QUESTION [1 upvotes]: Given domain $R$ and $\frac{a}{b}\in frac(R)$, suppose $\frac{a}{b}$ is integral over $R_\frak{m}$ for any maximal ideal ${\frak m}$ of $R$. Then is it right that $\frac{a}{b}$ is integral over $R$?
I know that $R$ is integral closed if and only if each localization w.r.t. a maximal ideal is integral closed. Can I solve my problem by this assertion?

REPLY [2 votes]: Let $K$ be the field of fractions of $R$, and suppose $x \in K$ is integral over each localization $R_{\mathfrak m}$.  Let
$$I = \{ r \in R : rx \textrm{ is integral over } R \}$$
Then $I$ is an ideal of $R$.  If we can show that
$$I_{\mathfrak m} = \{r \in R_{\mathfrak m} : rx \textrm{ is integral over } R_{\mathfrak m}\}$$
then we will have $I_{\mathfrak m} = R_{\mathfrak m}$ for all $\mathfrak m$, hence $I = R$.


TITLE: Proving every linear operator in the dual space is compact.
QUESTION [0 upvotes]: How can I prove that for $X$ being a Banach Space, every $\phi \in X^*$ is compact?

REPLY [2 votes]: Assume that $(x_{n})$ is a bounded sequence in $X$, then $(\phi(x_{n}))$ is also bounded, then Heine-Borel Theorem implies that $(\phi(x_{n}))$ has a convergent subsequence, so $\phi$ is compact.


TITLE: How find the possible eigenvalue of $P$
QUESTION [2 upvotes]: Question 1:
Let $P$ be a real matrix such that $$P^{T}=P^2$$ What are the possible eigenvalues of $P$? I consider sometimes, But I can't, and I guess $1$ and $-1$? Thank you
Question 2： if $P$ is complex matrix, such that $P^T=P^2$, then what are the possible eigenvalues of $P$?
Question 1 has been solved by Sami Ben Romdhane, but question 2 is still not solved.
Thank you very much!Thank you

REPLY [0 votes]: In order to complete the answer (in the case $P$ real matrix) one needs to provide examples of matrices which satisfy the relation $P^T=P^2$, and having each of the eigenvalues $\{0,1,\mathrm{e}^{2\pi i/3},\mathrm{e}^{4\pi i/3}\}$.
Such examples are $P=0$, with only one eigenvalue $\lambda=0$, $P=I$, with only one eigenvalue $\lambda=1$ and
$$
P=\left(\begin{matrix} \cos(2\pi/3) & \sin(2\pi/3) \\ -\sin(2\pi/3) & \cos(2\pi/3)
\end{matrix}\right).
$$


TITLE: Prove that $(a b+b c+c a-1)^{2} \leq\left(a^{2}+1\right)\left(b^{2}+1\right)\left(c^{2}+1\right)$.
QUESTION [1 upvotes]: Let $a$, $b$, and $c$ be real numbers.  Prove that $$(a b+b c+c a-1)^{2} \leq\left(a^{2}+1\right)\left(b^{2}+1\right)\left(c^{2}+1\right)\,.$$

In solution of this author take Let $a=\tan x, b=\tan y, c=\tan z$ with $-\frac{\pi}{2}<x, y, z<\frac{\pi}{2}$ but i did not understand the reason behind letting that $-\frac{\pi}{2}<x, y, z<\frac{\pi}{2}$ ,
i mean if we just take  $a=\tan x, b=\tan y, c=\tan z$ then is something wrong,
I do not want solution,just want to clear this step

REPLY [1 votes]: We have $$(a^2+1)(b^2+1)(c^2+1)-(ab+bc+ca-1)^2=(a+b+c-abc)^2\ge 0$$


TITLE: Zero-knowledge proof for $P \ne NP$?
QUESTION [5 upvotes]: In computational complexity, $P \ne NP$ is a widely believed conjecture. Suppose that someone discovered a proof for it. He wants to publish a proof that he correctly proved the conjecture. I am aware that NP-complete problems have Zero-knowledge proofs. Assuming $P \ne NP$, can we have Zero-knowledge proof (or morally equivalent one) for  $P \ne NP$?

REPLY [4 votes]: First of all, it does not really make sense to talk about zero-knowledge proofs for a single statement such as $P\ne NP$.  You really should be asking about whether there is a zero-knowledge proof for a computational problem, such as: "Given a statement $S$ in the first-order language of set theory, and a positive integer $n$, does there exist a ZFC-proof of $S$ of length at most $n$?"
With this reformulation, you have already partially answered your own question, by noting that there is a standard theorem about the existence of zero-knowledge proofs for any $NP$-complete language. However, there are two caveats to be aware of in that standard theorem. The first caveat is that it assumes the existence of a one-way function, which is a stronger assumption than $P\ne NP$. So if you only have the hypothesis $P\ne NP$ available to you, then that's not quite good enough.  The second caveat is that the usual proof relies on a commitment scheme, which has two parts to it, the binding part and the hiding part.  Ideally we'd like both parts to be statistically secure and not just computationally secure, but it turns out that it is impossible for both parts to be statistically secure unless the polynomial hierarchy collapses to the second level (Fortnow, "The complexity of perfect zero knowledge").  So if you want the strongest possible form of zero knowledge, then the answer to your question is likely no.


text:
/-
Copyright (c) 2017 Mario Carneiro. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
-/
import data.fintype.basic
import algebra.big_operators.ring
import algebra.big_operators.option

/-!
Results about "big operations" over a `fintype`, and consequent
results about cardinalities of certain types.

## Implementation note
This content had previously been in `data.fintype.basic`, but was moved here to avoid
requiring `algebra.big_operators` (and hence many other imports) as a
dependency of `fintype`.

However many of the results here really belong in `algebra.big_operators.basic`
and should be moved at some point.
-/

universes u v

variables {α : Type*} {β : Type*} {γ : Type*}

open_locale big_operators

namespace fintype

@[to_additive]
lemma prod_bool [comm_monoid α] (f : bool → α) : ∏ b, f b = f tt * f ff := by simp

lemma card_eq_sum_ones {α} [fintype α] : fintype.card α = ∑ a : α, 1 :=
finset.card_eq_sum_ones _

section
open finset

variables {ι : Type*} [decidable_eq ι] [fintype ι]

@[to_additive]
lemma prod_extend_by_one [comm_monoid α] (s : finset ι) (f : ι → α) :
  ∏ i, (if i ∈ s then f i else 1) = ∏ i in s, f i :=
by rw [← prod_filter, filter_mem_eq_inter, univ_inter]

end

section
variables {M : Type*} [fintype α] [comm_monoid M]

@[to_additive]
lemma prod_eq_one (f : α → M) (h : ∀ a, f a = 1) :
  (∏ a, f a) = 1 :=
finset.prod_eq_one $ λ a ha, h a

@[to_additive]
lemma prod_congr (f g : α → M) (h : ∀ a, f a = g a) :
  (∏ a, f a) = ∏ a, g a :=
finset.prod_congr rfl $ λ a ha, h a

@[to_additive]
lemma prod_eq_single {f : α → M} (a : α) (h : ∀ x ≠ a, f x = 1) :
  (∏ x, f x) = f a :=
finset.prod_eq_single a (λ x _ hx, h x hx) $ λ ha, (ha (finset.mem_univ a)).elim

@[to_additive]
lemma prod_eq_mul {f : α → M} (a b : α) (h₁ : a ≠ b) (h₂ : ∀ x, x ≠ a ∧ x ≠ b → f x = 1) :
  (∏ x, f x) = (f a) * (f b) :=
begin
  apply finset.prod_eq_mul a b h₁ (λ x _ hx, h₂ x hx);
  exact λ hc, (hc (finset.mem_univ _)).elim
end

/-- If a product of a `finset` of a subsingleton type has a given
value, so do the terms in that product. -/
@[to_additive "If a sum of a `finset` of a subsingleton type has a given
value, so do the terms in that sum."]
lemma eq_of_subsingleton_of_prod_eq {ι : Type*} [subsingleton ι] {s : finset ι}
    {f : ι → M} {b : M} (h : ∏ i in s, f i = b) : ∀ i ∈ s, f i = b :=
finset.eq_of_card_le_one_of_prod_eq (finset.card_le_one_of_subsingleton s) h

end

end fintype

open finset

section

variables {M : Type*} [fintype α] [comm_monoid M]

@[simp, to_additive]
lemma fintype.prod_option (f : option α → M) : ∏ i, f i = f none * ∏ i, f (some i) :=
finset.prod_insert_none f univ

end

open finset

@[simp] theorem fintype.card_sigma {α : Type*} (β : α → Type*)
  [fintype α] [∀ a, fintype (β a)] :
  fintype.card (sigma β) = ∑ a, fintype.card (β a) :=
card_sigma _ _

@[simp] lemma finset.card_pi [decidable_eq α] {δ : α → Type*}
  (s : finset α) (t : Π a, finset (δ a)) :
  (s.pi t).card = ∏ a in s, card (t a) :=
multiset.card_pi _ _

@[simp] lemma fintype.card_pi_finset [decidable_eq α] [fintype α]
  {δ : α → Type*} (t : Π a, finset (δ a)) :
  (fintype.pi_finset t).card = ∏ a, card (t a) :=
by simp [fintype.pi_finset, card_map]

@[simp] lemma fintype.card_pi {β : α → Type*} [decidable_eq α] [fintype α]
  [f : Π a, fintype (β a)] : fintype.card (Π a, β a) = ∏ a, fintype.card (β a) :=
fintype.card_pi_finset _

-- FIXME ouch, this should be in the main file.
@[simp] lemma fintype.card_fun [decidable_eq α] [fintype α] [fintype β] :
  fintype.card (α → β) = fintype.card β ^ fintype.card α :=
by rw [fintype.card_pi, finset.prod_const]; refl

@[simp] lemma card_vector [fintype α] (n : ℕ) :
  fintype.card (vector α n) = fintype.card α ^ n :=
by rw fintype.of_equiv_card; simp

@[simp, to_additive]
lemma finset.prod_attach_univ [fintype α] [comm_monoid β] (f : {a : α // a ∈ @univ α _} → β) :
  ∏ x in univ.attach, f x = ∏ x, f ⟨x, (mem_univ _)⟩ :=
fintype.prod_equiv (equiv.subtype_univ_equiv (λ x, mem_univ _)) _ _ (λ x, by simp)

/-- Taking a product over `univ.pi t` is the same as taking the product over `fintype.pi_finset t`.
  `univ.pi t` and `fintype.pi_finset t` are essentially the same `finset`, but differ
  in the type of their element, `univ.pi t` is a `finset (Π a ∈ univ, t a)` and
  `fintype.pi_finset t` is a `finset (Π a, t a)`. -/
@[to_additive "Taking a sum over `univ.pi t` is the same as taking the sum over
  `fintype.pi_finset t`. `univ.pi t` and `fintype.pi_finset t` are essentially the same `finset`,
  but differ in the type of their element, `univ.pi t` is a `finset (Π a ∈ univ, t a)` and
  `fintype.pi_finset t` is a `finset (Π a, t a)`."]
lemma finset.prod_univ_pi [decidable_eq α] [fintype α] [comm_monoid β]
  {δ : α → Type*} {t : Π (a : α), finset (δ a)}
  (f : (Π (a : α), a ∈ (univ : finset α) → δ a) → β) :
  ∏ x in univ.pi t, f x = ∏ x in fintype.pi_finset t, f (λ a _, x a) :=
prod_bij (λ x _ a, x a (mem_univ _))
  (by simp)
  (by simp)
  (by simp [function.funext_iff] {contextual := tt})
  (λ x hx, ⟨λ a _, x a, by simp * at *⟩)

/-- The product over `univ` of a sum can be written as a sum over the product of sets,
  `fintype.pi_finset`. `finset.prod_sum` is an alternative statement when the product is not
  over `univ` -/
lemma finset.prod_univ_sum [decidable_eq α] [fintype α] [comm_semiring β] {δ : α → Type u_1}
  [Π (a : α), decidable_eq (δ a)] {t : Π (a : α), finset (δ a)}
  {f : Π (a : α), δ a → β} :
  ∏ a, ∑ b in t a, f a b = ∑ p in fintype.pi_finset t, ∏ x, f x (p x) :=
by simp only [finset.prod_attach_univ, prod_sum, finset.sum_univ_pi]

/-- Summing `a^s.card * b^(n-s.card)` over all finite subsets `s` of a fintype of cardinality `n`
gives `(a + b)^n`. The "good" proof involves expanding along all coordinates using the fact that
`x^n` is multilinear, but multilinear maps are only available now over rings, so we give instead
a proof reducing to the usual binomial theorem to have a result over semirings. -/
lemma fintype.sum_pow_mul_eq_add_pow
  (α : Type*) [fintype α] {R : Type*} [comm_semiring R] (a b : R) :
  ∑ s : finset α, a ^ s.card * b ^ (fintype.card α - s.card) =
  (a + b) ^ (fintype.card α) :=
finset.sum_pow_mul_eq_add_pow _ _ _

@[to_additive]
lemma function.bijective.prod_comp [fintype α] [fintype β] [comm_monoid γ] {f : α → β}
  (hf : function.bijective f) (g : β → γ) :
  ∏ i, g (f i) = ∏ i, g i :=
fintype.prod_bijective f hf _ _ (λ x, rfl)

@[to_additive]
lemma equiv.prod_comp [fintype α] [fintype β] [comm_monoid γ] (e : α ≃ β) (f : β → γ) :
  ∏ i, f (e i) = ∏ i, f i :=
e.bijective.prod_comp f

/-- It is equivalent to sum a function over `fin n` or `finset.range n`. -/
@[to_additive]
lemma fin.prod_univ_eq_prod_range [comm_monoid α] (f : ℕ → α) (n : ℕ) :
  ∏ i : fin n, f i = ∏ i in range n, f i :=
calc (∏ i : fin n, f i) = ∏ i : {x // x ∈ range n}, f i :
  (equiv.subtype_equiv_right $ λ m, (@mem_range n m).symm).prod_comp (f ∘ coe)
... = ∏ i in range n, f i : by rw [← attach_eq_univ, prod_attach]

@[to_additive]
lemma finset.prod_fin_eq_prod_range [comm_monoid β] {n : ℕ} (c : fin n → β) :
  ∏ i, c i = ∏ i in finset.range n, if h : i < n then c ⟨i, h⟩ else 1 :=
begin
  rw [← fin.prod_univ_eq_prod_range, finset.prod_congr rfl],
  rintros ⟨i, hi⟩ _,
  simp only [fin.coe_eq_val, hi, dif_pos]
end

@[to_additive]
lemma finset.prod_to_finset_eq_subtype {M : Type*} [comm_monoid M] [fintype α]
  (p : α → Prop) [decidable_pred p] (f : α → M) :
    ∏ a in {x | p x}.to_finset, f a = ∏ a : subtype p, f a :=
by { rw ← finset.prod_subtype, simp }

@[to_additive] lemma finset.prod_fiberwise [decidable_eq β] [fintype β] [comm_monoid γ]
  (s : finset α) (f : α → β) (g : α → γ) :
  ∏ b : β, ∏ a in s.filter (λ a, f a = b), g a = ∏ a in s, g a :=
finset.prod_fiberwise_of_maps_to (λ x _, mem_univ _) _

@[to_additive]
lemma fintype.prod_fiberwise [fintype α] [decidable_eq β] [fintype β] [comm_monoid γ]
  (f : α → β) (g : α → γ) :
  (∏ b : β, ∏ a : {a // f a = b}, g (a : α)) = ∏ a, g a :=
begin
  rw [← (equiv.sigma_fiber_equiv f).prod_comp, ← univ_sigma_univ, prod_sigma],
  refl
end

lemma fintype.prod_dite [fintype α] {p : α → Prop} [decidable_pred p]
  [comm_monoid β] (f : Π (a : α) (ha : p a), β) (g : Π (a : α) (ha : ¬p a), β) :
  (∏ a, dite (p a) (f a) (g a)) = (∏ a : {a // p a}, f a a.2) * (∏ a : {a // ¬p a}, g a a.2) :=
begin
  simp only [prod_dite, attach_eq_univ],
  congr' 1,
  { convert (equiv.subtype_equiv_right _).prod_comp (λ x : {x // p x}, f x x.2),
    simp },
  { convert (equiv.subtype_equiv_right _).prod_comp (λ x : {x // ¬p x}, g x x.2),
    simp }
end

section
open finset

variables {α₁ : Type*} {α₂ : Type*} {M : Type*} [fintype α₁] [fintype α₂] [comm_monoid M]

@[to_additive]
lemma fintype.prod_sum_elim (f : α₁ → M) (g : α₂ → M) :
  (∏ x, sum.elim f g x) = (∏ a₁, f a₁) * (∏ a₂, g a₂) :=
by { classical, rw [univ_sum_type, prod_sum_elim] }

@[to_additive]
lemma fintype.prod_sum_type (f : α₁ ⊕ α₂ → M) :
  (∏ x, f x) = (∏ a₁, f (sum.inl a₁)) * (∏ a₂, f (sum.inr a₂)) :=
by simp only [← fintype.prod_sum_elim, sum.elim_comp_inl_inr]

end

subset_name: curated


TITLE: Given that $\tan\left(x-y\right) = k$ and $\tan\left(x\right) = 1$, express $\tan\left(y\right)$ in terms of $k$
QUESTION [0 upvotes]: Just looking for help on this particular question:
Given that $\tan (x - y) = k$ and $\tan(x) = 1$, express $\tan(y)$ in terms of $k$**
So far I've used the trig identity: $\tan(A±B) = (\tan(A)±\tan(B)) / (1 ∓ \tan(A)\tan(B))$
This got me to $(1-\tan(y))/(1+\tan(y))=k$, but I'm unsure where to go from here and struggle with solving these types of equations. From here, I tried to multiply the fraction by $(1-\tan(y))/(1-\tan(y))$, but this didn't help.
Thanks!
Toby.

REPLY [2 votes]: Hint:
Use the identity:
$$\tan(x-y) =\frac{\tan x - \tan y}{1 + \tan x\tan y} = k$$
Now factorise $\tan y$ out
$$k + k \tan y = 1 - \tan y $$
$$ \tan y (k+1) = 1 - k$$
You can finish it off from here

REPLY [1 votes]: Hint: Assuming your equation $$\frac{1-\tan y}{1 + \tan y} = k$$ is correct,
note that you can write
$$\frac{1-\tan y}{1 + \tan y} = \frac{2}{1 + \tan y}-1$$
Replace the LHS of your equation with this. You should see how to isolate $\tan y$ now.
Addendum: Completing since another answer has been accepted.
$$\frac{1-\tan y}{1 + \tan y} = k$$
$$\frac{2}{1 + \tan y}-1 = k\tag{rewrite LHS}$$
This is a very nice form because now "$\tan y$" appears in only one place. We can immediately solve for "$\tan y$":
$$\frac{2}{1 + \tan y}= 1+k\tag{add $1$}$$
$$\frac{1}{1 + \tan y} = \frac{1+k}{2}\tag{div. by $2$}$$
$$1 + \tan y = \frac{2}{1+k}\tag{invert}$$
$$\tan y = \frac{2}{1+k}-1\tag{subtr. $1$}$$
It may be a little nicer to combine these terms:
$$\tan y = \frac{1-k}{1+k}\tag{rewrite RHS}$$
To sum up, our first step put the equation in a nice form. It's nice because you can immediately see that the LHS was created from "$\tan y$" by successively performing the steps "add $1$, invert, multiply by $2$, subtract $1$". So we just need to undo these steps in reverse order on both sides to obtain "$\tan y$" on the LHS, and the RHS becomes whatever it becomes since it's along for the ride.
Addendum 2: The "trick" to nicing up the original form is to note that you can do this sort of thing:
$$\frac{a+b\;\boxed{X}}{c+d\;\boxed{X}}=\frac{a+\frac{b}{d}(dX)}{c+dX}=\frac{a -\frac{b}{d}(c)+\frac{b}{d}(c+dX)}{c+dX}$$
$$=\frac{\left(a -\frac{bc}{d}\right)}{c+d\;\boxed{X}} +\left(\frac{b}{d}\right)$$
All the stuff in parentheses is just some number, and now the "$X$" is by itself in one spot.


TITLE: Is it true that if $f(x)$ has a linear factor over $\mathbb{F}_p$ for every prime $p$, then $f(x)$ is reducible over $\mathbb{Q}$?
QUESTION [14 upvotes]: We know that $f(x)=x^4+1$ is a polynomial irreducible over $\mathbb{Q}$ but reducible over $\mathbb{F}_p$ for every prime $p$.
My question is:

Is it true that if $f(x)$ has a linear factor over $\mathbb{F}_p$ for every prime $p$, then $f(x)$ has a linear factor over $\mathbb{Q}$?

Edit: Thanks for @Jyrki Lahtonen's answer, I want to do some modifications:

Is it true that if $f(x)$ has a linear factor over $\mathbb{F}_p$ for every prime $p$, then $f(x)$ is reducible over $\mathbb{Q}$?

Thanks in advance!

REPLY [1 votes]: The idea used by user14972 in their answer can be used to find other examples:
$f(x)=(x^2+3)(x^3+2)$. How many zeroes the cubic factor has in $\Bbb F_p$ depends on which quadratic form of discriminant $D=-108=-3\cdot6^2$, if any, represents $p$; if 3 zeroes, $a^2+27b^2$; if no zeroes, $4a^2+2ab+7b^2$; if one zero, neither quadratic form. If that cubic factor has no zeroes, then $-108$ is a square $c^2$; $p>3$ so 6 has an inverse, and $(6^{-1}c)^2+3=0$.
Similarly, $f(x)=(x^2+3)(x^3+3)$, $D=-243=-3\cdot9^2$.
user14972's example, and the two above, use the characteristic cubic of quadratic forms whose discriminants have some value $D$ where $h(D)=3$, i.e. where quadratic forms of discriminant $D$ are in three classes. But it is not necessary to use such concepts of quadratic form theory.
If $p=3$ or $p=1\mod 6$, then $p$ has the form $a^2+3b^2$, so $0=(a^2+3b^2)b^{-2}=(ab^{-1})^2+3$. So, if $x^2+3$ has no zeroes in $\Bbb F_p$, then $p=2$ or $p=5\mod6$, so everything is a cube.[1] So we may take $f(x)=(x^2+3)(x^3+a)$ where $a$ is any integer except a cube (so that $f$ has no linear factor in $\Bbb Q$).
[Brandl][2] gives the example $f(x)=(x^2+x+1)(x^3-2)$. The following proof that $f$ has a zero in each $\Bbb F_p$ is adapted from [Brandl]. If $p\ne 1\mod 3$, then the order of the multiplicative group of $\Bbb F_p$ is not divisible by 3. Hence 2 is a cube modulo $p$.[1] If $p=1\mod 3$, then there exists a primitive cube root of unity $x$ modulo $p$. [This follows from Sylow's first theorem.]
This is obviously a root of the polynomial $x^2+x+1$. [This is because $0=x^3-1=(x-1)(x^2+x+1)$ but $x\ne 1$.]
[1] Proof. If $p=2$ or 3, $a^3=a$. If $p=6k+5$, then, by Fermat's little theorem, $a=a^p=a^{6k+5}$, so $a=r^3$ where $r=a^{4k+3}$. Alternatively, if any element of $\Bbb F_p$ were not a cube, then, by the pigeonhole principle, at least two unequal elements $a, b$ must have equal cubes. Then $0=a^3-b^3=(a-b)(a^2+ab+b^2)$; $a-b\ne 0$ so $a^2+ab+b^2=0$. The only element whose cube is 0 is 0, so $b\ne 0$, so $b$ has an inverse.
So $(a^2+ab+b^2)b^{-2}=0$ so $c^2+c+1=0$ where $c=ab^{-1}$. So $0=(c^2+c+1)(c-1)=c^3-1$ so $c^3=1$. $a\ne b$ so $c\ne 1$, so $c$'s order is 3, so $3\mid p-1$, contradiction.
[2] Rolf Brandl, Daniela Bubboloni and Ingrid Hupp. Polynomials with roots mod $p$ for all primes $p$. J. Group Theory 4 (2001), p.233--239.


TITLE: Frobenius theorem: a variant?
QUESTION [1 upvotes]: In a physics article I am reading [1] the author uses the following result, which he named Frobenius theorem:
If a vector field $F: \mathbb{R}^3 \rightarrow \mathbb{R}^3$ satisfies
$$F \cdot (\nabla \times F) = 0,\ \ \ \ \ \ \text{(A)}$$
denoting scalar product and vector product in this order, then there exists scalar fields $\lambda$ and $V$ such that $F = -\lambda \nabla V$.
The only relevant Frobenius theorem I can think of is the one in differential calculus but it is about linear PDEs whereas the equation (A) is quadratic in $F$. Thus I failed to find the connection. Did I miss something? Or is there another Frobenius theorem?
[1] H Urbantke, Force fields in which all orbits are planar, European Journal of Physics 7 (1986), 157

REPLY [3 votes]: There are indeed a lot of cosmetically different "Frobenius theorem"s around. You shouldn't be thinking of the $F \cdot \nabla \times F = 0$ as the first-order PDE here - rather, it is the involutivity condition.
One convenient formulation of Frobenius is the following:

If $\omega$ is a differential one-form satisfying $\omega \wedge d\omega = 0$, then locally we can find smooth functions $f,g$ such that $\omega = f\,d g$.

Letting $\omega = F^\flat$ be the one-form corresponding to $F$, we can translate from three-dimensional vector calculus to exterior calculus: we have $$F \cdot (\nabla \times F) dV = \langle \omega, \star\,d \omega \rangle dV = \omega \wedge d \omega = 0$$ and thus there exist $f,g$ such that $\omega = f\,dg$ and thus $F = f\nabla g$.


TITLE: Existence of spin-$\frac{1}{2}$ representation corresponds to $\text{SO}(3)$ having double cover?
QUESTION [5 upvotes]: I come across this article:
https://skullsinthestars.com/2016/03/29/1975-neutrons-go-right-round-baby-right-round/
I quote here a part of this article:

Spin 1/2 particles like the electron, proton and neutron, which constitute all of ordinary matter, must be rotated 2 times in order to look the same: a full 720°! This is incredibly bizarre, and there really isn’t anything in the world we experience that is comparable.

I am concerned about these two sentences quoted. Let me first state what I know:

The Lie group $\text{SO}(3)$ has fundamental group $\Bbb Z_2$. Equivalently, we say that the universal cover of $\text{SO}(3)$ is a double cover.
The belt trick is a demonstration of the fact that $\text{SO}(3)$ has universal cover being double cover. In terms of fundamental group, a 360° rotation in 3D space is not homotopic to the identity, while a 720° rotation is homotopic to the identity.

The quoted article talks about belt trick (the "rotate 720° to go back to original state" thing) as if it is related to spin-$\frac{1}{2}$ particles, that these particles are examples which 360° rotation will not give the original state, but 720° rotation will. They seem to imply that the very existence of spin-$\frac{1}{2}$ representation of $\mathfrak{so}(3)$ (those Pauli matrices used to describe spin-$\frac{1}{2}$) is connected to the fact that $\text{SO}(3)$ has double universal cover. Is this even true, that spin-$\frac{1}{2}$ representation is related to $\text{SO}(3)$ having double cover?
This answer by ACuriousMind seems to be related, but I am not sure if that directly answers my question.
Extra added question:
The article also states something like "spin-$2$ particle returns to its original state after 180° rotation". I believe this is also a false claim, is it not?

REPLY [12 votes]: To clarify the misunderstanding arising from the text you have read, I should explain some general notions and result about the representation of $SO(3)$, viewed as the group of spatial rotations in the Hilbert space of a quantum system.
It is also fundamental in our discussion to bring in our mind that a state is a unit vector up a phase.
As is well known,  symmetries are represented by unitary operators (also antiunitary but when dealing with connected Lie groups they do not take place). The physical group of rotations $SO(3)$ acts on states, spin states in particular, and this action is expected to preserve the group structure.
As a consequence  the map $$SO(3) \ni R \mapsto U_R\tag{1}$$ associating unitary operators $U_R$ to physical rotations $R\in SO(3)$ and representing the action in the space of the states of the rotations of the physical system must satisfy $$U_I= \alpha I\:, \quad U_RU_{R'}= \omega(R,R')U_{RR'}\tag{2}$$
where $\alpha, \omega(R,R')$ are phases: unit-modulus complex numbers (in principle they could also depend on the state in the argument of the unitary operators, but it is easy to prove that this dependence is actually trivial).
A map satisfying (2) is said to be a projective unitary representation.
This is the best you can obtain from basic assumptions of Quantum Physics when dealing with groups of physical symmetries.
Another important requirement is that the map (1) is continuous in a physical sense: for every pair of unit vectors $\psi, \phi$, the transition probability
$$SO(3) \ni R \mapsto |\langle \psi|U_R \phi \rangle|^2$$
has to be continuous in the variable $R\in SO(3)$.
It is evident that unitary representations ($\alpha=\omega(R,R')=1$) are much more handy than projective unitary representations, so that mathematical physicists studied the problem of reducing projective unitary representations to properly unitary ones.
A celebrated theorem due to Bargmann established that, if the Lie algebra of the represented group $G$, $SO(3)$ in our case, has a certain cohomological property and the group is simply connected, then for a given continuous projective unitary representation of that group, it is always possible to redefine
$U_g \to \chi_g U_g =: V_g$ (where $\chi_g$ is a suitable phase) in order that the new map
$$G \ni g \mapsto V_g\tag{1'}$$
is a continuous unitary representation,
$$V_e=  I\:, \quad V_gV_{g'}= V_{gg'}\tag{2'}\:.$$
What happens for $G=SO(3)$?
Well, the cohomological condition is in fact fulfilled, but $SO(3)$ is not simply connected.
However one can pass to deal with $SU(2)$ which is the universal covering (double covering actually) of $SO(3)$. From definition of universal covering, on the one hand it has the same Lie algebra of $SO(3)$, so that the cohomological condition is safe, on the other hand it is simply connected.
The crucial observation is that, again because $SU(3)$ is the universal covering of $SO(3)$, there is a surjective Lie-group homomorphism which is a local isomorphism around the identity
$$\Pi: SU(2) \to SO(3)\:.$$
It holds $ker(\Pi) = \{\pm I\}$, so that there are exactly two matrices of $SU(2)$ corresponding to a matrix of $SO(3)$ and these matrices differ only for their sign:
$$\Pi^{-1}(R) = \{\pm A_R\}\:.\tag{3}$$
According to the theory outlined above and the general theory of irreducible representations (Schur's lemma) of compact topological groups (the Peter-Weyl theorem), it is possible to prove that, all irreducible continuous unitary representations of $SU(2)$ are
(i) finite-dimensional and
(ii) they include all possible irreducible continuous unitary projective representations of $SO(3)$. In  the sense that if (1) and (2) holds for a given continuous projective unitary representation $U$ of $SO(3)$, it is then possible to change the phases
$$V_R := \chi_R U_R$$ in order that
either
(a) $SO(3) \ni R \mapsto V_R$ is an irreducible  continuous unitary representation of $SO(3)$
or
(b) it still holds  $V_{R}V_{R'} \neq V_{RR'}$ (so that $V$ remains a projective unitary rep. of $SO(3)$) but
$SU(2) \ni A \mapsto V_{\Pi(A)}$ is an irreducible  continuous unitary representation of $SU(2)$
In the second case the representation of $SO(3)$ is still projective unitary, but we perfectly know how it is far from a properly unitary one: it is indeed possible to prove that $V_I=I$ and $V_RV_{R'} = \pm V_{RR'}$.
Cases (a) and (b) are distinguished  by a parameter labeling the representations: it is nothing but the $j=0,1/2,1,3/2, \ldots$ in the expression $j(j+1)$ of the  eigenvalue of $J^2$ which physicists known very well.
(a) is proper of integer spin representations and (b) is proper of semi-integer spin representation.
We are ready to come back to the misunderstanding about $4\pi$.
Consider a spin-$1/2$ representation. In this case the Hilbert space is $\mathbb{C}^2$ and from the point of view of $SU(2)$, the representation is $SU(2) \ni A \mapsto A= V_{\Pi(A)}$.
From the point of view of $SO(3)$ the representation is strictly projective. The fundamental observation is this one. Consider the group of  rotations $R_\theta$ of $SO(3)$ around an axis ${\bf n}$. This is a one-parameter subgroup of $SO(3)$ which is the image through $\Pi$ of an analogous one-parameter subgroup of $SU(2)$ denoted by $A_\theta$.
It turns out that this subgroup of $SU(2)$ is completely covered by taking $\theta \in [0, 4\pi]$ with in particular $$A_0=I, \quad A_{2\pi}= -I,\quad A_{4\pi}=I.$$
This is coherent with (3), since $\Pi(\pm I) = I$.
If $\psi \in \mathbb{C}^2$, we have that
$$V_{\pi(A_{2\pi})}\psi = A_{2\pi}\psi = -\psi \tag{4}$$
whereas
$$V_{\pi(A_{4\pi})}\psi = A_{4\pi}\psi = \psi\tag{5}$$
(4) and (5) lead to the  misunderstanding  that a rotation of $2\pi$ changes the state of a spin-$1/2$ particle and that a rotation of $4\pi$ is necessary to restore the initial state. This is false because a state is a unit vector up to a phase so that $\psi$ and $-\psi$ in particular define the same state.
Furthermore, we must not forget that the physical group we are representing is not $SU(2)$ but $SO(3)$ (even if the resulting representation is projective unitary). From the point of view of physics, $A_{2\pi}$ and $A_{4\pi}= -A_{2\pi}$ define the same rotation $\Pi(A_{2\pi})= \Pi(A_{4\pi}) =R_{2\pi}= I$.
Just a final remark. The partition into (a) and (b) of the continuous projective unitary representations of $SO(3)$ has non-negligible physical consequences. It gives rise to a superselection rule, but this is not the place where discussing it.
Regarding your last extra question: according to what I wrote above, the considered representation is now a proper unitary representation of $SO(3)$. I do not know how it is made, but it is possible that a rotation of $SO(3)$ around an axis of $\pi$ produces $e^{ia}I$. These matrices can be found in the literature and it is easy to check.


TITLE: Proof of superlinear convergence of quasi-Newton methods in Nocedal & Wright
QUESTION [2 upvotes]: I am reading Numerical Optimization by Nocedal & Wright, and I am having trouble understanding some aspects of the proof of Theorem $3.7$. I have been stuck on this theorem for many hours, so any help is greatly appreciated.
There are two things I don't understand:

The theorem is an iff statement. The author proves one direction, but I don't see how to prove the reverse.

The author seems to use the assumption that the Hessian is Lipschitz, but this is not an explicit assumption of the theorem. Is this a mistake from the author? (I checked the errata and this wasn't on there)

The following are several lines the author references in the proof. The theorem and the proof follows.

$$\|x_k + p_k^N - x^*\| \le L\|x_k - x^*\|^2 \tag{3.33}$$
(The above is where my point #2 comes from. This inequality was derived in the proof of an earlier theorem about quadratic convergence of Newton's Method and in that theorem we had a hypothesis that the Hessian is Lipschitz, which was used to prove the above inequality.)
$$p_k = -B_k^{-1} \nabla f_k \hspace{1cm} \tag{3.34}$$
where $B_k$ is symmetric and pos. def.,
$$\lim_{k \to \infty} \frac{\|(B_k - H_f(x^*))p_k\|}{\|p_k\|} = 0 \tag{3.36}$$

Theorem $\textbf{3.7}$: Suppose that $f:\mathbb{R}^n \to \mathbb{R}$ is twice continuously differentiable. Consider the iteration $x_{k+1} = x_k + p_k$ (that is, the step length $\alpha_k$ is uniformly $1$) and that $p_k$ is given by $(3.34)$. Let us assume also that $(x_k)$ converges to a point $x^*$ such that $\nabla f(x^*) = 0$ and $H_f(x^*)$ is positive definite. Then $(x_k)$ converges superlinearly if and only if $(3.36)$ holds.

Proof: We first show that $(3.36)$ is equivalent to
$$p_k - p_k^N = o(\|p_k\|) \tag{3.37}$$
where $p_k^N = - H_f(x_k)^{-1} \nabla f_k$ is the Newton step. Assuming $(3.36)$ holds, we have that
\begin{align*}
p_k - p_k^N & = H_{f}(x_k)^{-1}(H_f(x_k)p_k + \nabla f_k)\\
&= H_{f}(x_k)^{-1}(H_{f}(x_k) - B_k)p_k\\
&= O(\|(H_f(x_k) - B_k)p_k\|)\\
&= o(\|p_k\|)
\end{align*}
where we have used the fact that $\|H_f(x_k)^{-1}\|$ is bounded above for $x_k$ sufficiently close to $x^*$, since the limiting Hessian $H_f(x_*)$ is positive definite. The converse follows readily of we multiply both sides of $(3.37)$ by $H_f(x_k)$ and recall $(3.34)$.

By combining $(3.33)$ and $(3.37)$, we obtain that
$$\|x_k+p_k-x^*\| \le\|x_k+p_k^N-x^*\|+\|p_k-p_k^N\|=O(\|x_{k}-x^*\|^2)+o(\|p_k\|).$$
A simple manipulation of this inequality reveals that $\|p_k\| = O(\|x_k - x^*\|),$ so we obtain
$$\|x_k+p_k-x^*\| \le o(\|x_k-x^*\|),$$
giving the superlinear convergence result.

REPLY [4 votes]: The proof of this theorem does have a few places to be patched up. For Question 2, the proof uses (3.33) but it only needs a weaker form:\begin{gather*}
x_k + p^N_k - x^* = o(\|x_k - x^*\|) \quad (k → ∞),\tag{3.33$'$}
\end{gather*}
In fact, by the Taylor expansion,$$
∇f(x) = ∇f(x^*) + Hf(x^*) (x - x^*) + o(\|x - x^*\|) \quad (x → x^*).
$$
Note that $∇f(x^*) = \boldsymbol{0}$, $p^N_k = -(Hf(x_k))^{-1} ∇f(x_k)$, and $\|(Hf(x))^{-1}\|$ is bounded in the neighborhood of $x^*$. Because $(Hf(x))^{-1} Hf(x^*) → I$ as $x → x^*$, so\begin{align*}
&\mathrel{\phantom{=}}{} x_k + p^N_k - x^* = (x_k - x^*) - (Hf(x_k))^{-1} ∇f(x_k)\\
&= (x_k - x^*) - (Hf(x_k))^{-1} Hf(x^*) (x_k - x^*) + o(\|x_k - x^*\|)\\
&= (I -  (Hf(x_k))^{-1} Hf(x^*)) (x_k - x^*) + o(\|x_k - x^*\|)\\
&= o(\|x_k - x^*\|) \quad (k → ∞).
\end{align*}
Now for question 1, since (3.36) and (3.37) are equivalent, it suffices to prove that$$
x_k + p_k - x^* = o(\|x _k- x^*\|) \ (k → ∞) \Longleftrightarrow p_k - p^N_k = o(\|p_k\|) \ (k → ∞).
$$
On the one hand, if $p_k - p^N_k = o(\|p_k\|)$ ($k → ∞$), then$$
\|p_k\| - \|p_k - p^N_k\| \leqslant \|p^N_k\| \leqslant \|p_k\| + \|p_k - p^N_k\|
$$
implies that $\|p^N_k\| \sim \|p_k\|$ ($k → ∞$), so\begin{gather*}
p_k - p^N_k = o(\|p_k\|) = o(\|p^N_k\|)\\
= o(\|(Hf(x_k))^{-1} (x_k - x^*)\|) = o(\|x_k - x^*\|) \quad (k → ∞).
\end{gather*}
Combining with $\|x_k + p_k - x^*\| \leqslant \| x_k + p^N_k - x^*\| + \|p_k - p^N_k\|$ and (3.33$'$) yields$$
x_k + p_k - x^* = o(\|x_k - x^*\|) \quad (k → ∞).
$$
On the other hand, if $x_k + p_k - x^* = o(\|x _k- x^*\|)$ ($k → ∞$), then$$
\|p_k - p^N_k\| \leqslant \|x_k + p_k - x^*\| + \| x_k + p^N_k - x^*\|
$$
and (3.33$'$) imply that$$
\|p_k - p^N_k\| = o(\|x_k - x^*\|) = o(\|p^N_k\|) \quad (k → ∞).
$$
Combining with$$
\|p^N_k\| - \|p_k - p^N_k\| \leqslant \|p_k\| \leqslant \|p^N_k\| + \|p_k - p^N_k\|
$$
yields $\|p_k\| \sim \|p^N_k\|$ ($k → ∞$) and$$
\|p_k - p^N_k\| = o(\|p^N_k\|) = o(\|p_k\|) \quad (k → ∞).
$$


TITLE: Finding triangles in a graph: other approaches besides property testing?
QUESTION [8 upvotes]: We're working on a paper that presents some algorithms for finding triangles and network motifs (constant size subgraphs, also known as graphlets) in a distributed setting. We characterize the tradeoff between the number of triangles in the graph and the communication load necessary. I am looking for references to work done on this question in the centralized model.
The problem is that nearly everything I found on this topic that had a theoretical flavor to it was within the framework of property testing. To illustrate the difference - consider the case of a graph with $n$ vertices, that is comprised of $n-2$ triangles all sharing the edge $\left(1,2\right)$. From the point of view of property testing, this graph is very close to be triangle-free (removing that critical edge does the job), whereas it has a linear number of triangles, which is a lot by our standards.
Any references at all will be appreciated.
Edit: I'm mainly interested in algorithms that can determine whether the graph contains triangles quickly. For triangle (or other subgraph) listing algorithms, the running time is naturally bounded from below by the number of triangles in the graph, as the algorithm needs to list them all, making such instances harder in a sense. From the point of view of a decision problem ("triangle-free or not"), having many triangles actually makes the problem easier, since you can easily find one.

REPLY [3 votes]: In the comments to David Eppstein's answer you ask for the domain of query complexity. I think what you describe has no papers written on it, because it has a trivial (deterministic, or randomized) query complexity lower bound of $\Omega(n^2)$ (where $n$ is the number of vertexes, so $O(n^2)$ is input size, and thus max query complexity).

If you want to see why, consider the following graph family:
Define a graph $G_{0}$ as: there is a special vertex $v$, and two partitions $X$ and $Y$ of size $(n - 1)/2$. There is an edges between each vertex in $X$ and $v$ and between each vertex in $Y$ and $v$.
For $i \in X$ and $j \in Y$ define a graph $G_{ij}$ as $G_0$ with the edge $ij$ added.
$G_0$ has not triangles, and each $G_{ij}$ has 1 triangle. Given the promise that you graphs is either $G_0$ or $G_{ij}$ for some $i$ and $j$ is obviously equivalent to unordered search on $(n - 1)^2/4$ objects (the edges).


TITLE: Hölder continuous but not differentiable function
QUESTION [10 upvotes]: How can it be proved that the function $$f(x)=\sum_{n=1}^{\infty}2^{-n\alpha}\cos(2^nx)$$ for $\alpha \in ]0,1[$ is $\alpha$-Hölder  continuous but not differentiable at any point of $[0,1]$?
I tried to write down $f(x+h)-f(x)$ and use addition formulas for the cosine, but I don't obtain anything..

REPLY [11 votes]: This is one of the well know examples of Weierstrass function. Hardy studied Hölder-continuity of such functions in  Weierstrass's nondifferentiable function, G.H. Hardy, Trans. Amer. Math. Soc., 17 (1916), 301–325.. Here is a proof of Hölder-continuity for your case.
Theorem. Let $0<a<1$, $b>1$ and $ab>1$ then the function
$$
f(x)=\sum\limits_{n=1}^\infty a^n\cos(b^n x)
$$
is $(-\log_b a)$-Hölder continuous.
Proof.
Consider $x\in\mathbb{R}$ and $h\in(-1,1)$, then
$$
f(x+h)-f(x)=
\sum\limits_{n=1}^\infty a^{n}(\cos(b^n(x+h))-\cos(b^nx))=
$$
$$
-2\sum\limits_{n=1}^\infty a^{n}\sin(2^{-1}b^n(2x+h))\sin(2^{-1}b^{n}h)=
$$
Since $b>1$ and $h\in(-1,1)$ there exist $p\in\mathbb{N}$ such that $2^{-1}b^{p}|h|\leq 1<b^p|h|$, so
$$
|f(x+h)-f(x)|\leq
2\sum\limits_{n=1}^\infty a^{n}|\sin(2^{-1}b^{n}(2x+h))||\sin(2^{-1}b^{n}h)|\leq
2\sum\limits_{n=1}^\infty a^{n}|\sin(2^{-1}b^{n}h)|=
$$
$$
2\sum\limits_{n=1}^p a^{n}|\sin(2^{-1}b^{n}h)|+
2\sum\limits_{n=p+1}^\infty a^{n}|\sin(2^{-1}b^{n}h)|\leq
2\sum\limits_{n=1}^p a^{n}|2^{-1}b^{n}h|+
2\sum\limits_{n=p+1}^\infty a^{n}=
$$
$$
\frac{ab|h|}{ab-1}(a^p b^p-1)+\frac{2a}{1-a}a^p\leq
\frac{ab|h|}{ab-1}a^p b^p+\frac{2a}{1-a}a^p
$$
Since $2^{-1}b^{p}|h|\leq 1<b^p|h|$ and $0<a<1$, then we have $b^p|h|<2$ and $a^p\leq |h|^{-\log_b a}$. Hence
$$
|f(x+h)-f(x)|\leq
\frac{ab|h|}{ab-1}a^p b^p+\frac{2a}{1-a}a^p\leq
\frac{2ab}{ab-1}a^p +\frac{2a}{1-a}a^p\leq
$$
$$
\left(\frac{2ab}{ab-1} +\frac{2a}{1-a}\right)|h|^{-\log_b a}=
\frac{b-1}{(ab-1)(1-a)}|h|^{-\log_b a}
$$
This means that $f$ is $(-\log_b a)$-Hölder continuous.
Corollary. For $\alpha\in(0,1)$ the function
$$
f(x)=\sum\limits_{n=1}^\infty 2^{-n\alpha}\cos(2^n x)
$$
is $\alpha$-Hölder continuous.
Proof Apply previous theorem with $a=2^{-\alpha}$ and $b=2$.
As for the proof of nowhere differentiability, I don't know a short proof. The problem is that the standard Weierstrass argument  is not applicable here - parameters $a$, $b$ must satisfy inequality $ab>1+\frac{3\pi}{2}$. So it seems to me that one should repeat all the steps of Hardy's proof.


TITLE: Expanding universe space through matter or matter through space?
QUESTION [2 upvotes]: So the universe is expanding, rather space is expanding. By expanding we mean space is coming into existence at all points.
Is that an equal rate of expansion everywhere?
Now the expansion does not over come the force holding matter together, planetary systems, galaxies even galactic clusters to some extent. Larger scales than that and things are moving apart.
Is it that space is not expanding within the smaller structures or is space expanding through these structures?

REPLY [4 votes]: You ask:

Is it that space is not expanding within the smaller structures or is space expanding through these structures?

where I've highlighted what I think is the key issue.
The phrase space is expanding is a convenient metaphor to describe the expansion of the universe, but it is only a metaphor and taking it too literally can lead to confusion. It this case it's leading you to ask if space is somehow sliding past gravitationally bound masses. Or to use the rubber sheet analogy: if we model the expansion of the universe by an expanding rubber sheet, does that mean gravitationally bound masses are sliding over the sheet so they can stay together while the sheet expands?
The expansion of spacetime has a precise technical meaning that is derived from the FLRW metric that describes our universe on the large scale. If we use coordinates in which spacetime is isotropic and homogeneous then the proper distance between any two points in space is a function of time. Yes, we can describe this as space expanding, but this is an interpretation that is specificially linked to the FLRW metric.
The problem is that near a massive body spacetime is no longer described by the FLRW metric. If we consider a single massive body then very close to that body spacetime will be described by the Schwarzschild metric. This is time independant and there is no sense in which it describes an expanding, or contracting, or changing in any way spacetime. The concept simply isn't appropriate. Far enough away from that body that its gravity becomes negligable we're back into a region of spacetime described by the FLRW metric, and we can use expanding spacetime as a reasonable interpretation of the geometry.
The point I am trying to make is that your question doesn't have an answer because it doesn't mean anything. And it doesn't mean anything because you've taken a concept (expansion of spacetime) that is specifically linked to the FLRW metric and tried to apply it when the FLRW metric doesn't apply.


TITLE: What is the effect of frequency of light on reflection from a surface?
QUESTION [1 upvotes]: Suppose we have a light source with a frequency $f$. The light source shines on a surface with known properties (eg. texture, material, etc.) for example a sheet of unpolished steel. What is the effect of frequency (increasing or decreasing it) on the intensity of reflection from the surface? Does it have any effect at all? What about the reflection's angle?

REPLY [1 votes]: The reflection coefficient is indeed a function of frequency.  You know this but probably did not think about it.  A red surface reflects red light more than blue,  maybe.  For each material and surface quality there is a specific dependence on frequency. The metals like silver or aluminum may reflect all visible frequencies about the same (but not UV light). Gold and copper reflect more yellow-red. The angle of reflection though is not a function of frequency.