TITLE: Detect compass disturbance
QUESTION [1 upvotes]: I am looking for a way to determine wether the compass of a phone is  showing inaccurate north heading by looking at magnetometer values.
Right now I have been looking at total magnetic field strength: Math.sqrt((x * x) + (y * y) + (z * z));. When disturbing the compass of the phone with metal - and when seeing the compass needle  pointing the wrong way - I look at the teslameter and it deviates +- 8μT or more.
Is it a correct assumption I can detect a faulty compass heading by comparing the total magnetic strength. And would it be better to look at the vectors independently and compare them instead. If so how?

It can be noted I am using calibrated magnetic field which is supposed to give readings without device bias mentioned here. And that I have checked out raw device magnetometer data of which was not recommended and hard to understand.

Update:
These stack overflow answers and this AHRS algorithm suggest it is possible.

REPLY [1 votes]: Cellphone magnetometers are operated as ratiometric devices; the cell phone produces a bearing and possibly a magnetic dip by applying trigonometry to ratios of the measurements. This means that there is no strong demand for any absolute accuracy in the magnetometer chips output. Manual calibration is used to recalibrate both the relative gains of each of the three 1D magnetometers, and their offsets.

Is it a correct assumption I can detect a faulty compass heading by comparing the total magnetic strength.

The short answer is No, at least not easily.
Let's look at what can cause a faulty compass heading:

bad or out-of-date calibration
"soft-iron" errors (refers to nearby ferromagnetic materials that interact with the Earth's field and produce a local distortion that affects your compass)
"hard-iron" errors (refers to nearby magnetized materials (or other sources of DC magnetic fields) that adds to the Earth's field and affects your compass)

A bad or out-of-date calibration might be detectable if you measure at many orientations (as shown below) and determine that $S$ is not constant. But an easier way to detect that would be to simply do the calibration again and see if the heading changes.
"Soft-iron" and "hard iron" errors would be difficult to detect for the following reason. The local geomagnetic field strength is not very predictable. The Earth's average field at your coordinates can be looked up somewhere, but local geolocial effects can perturb it substantially. See Is there a “submerged object” in Australia that causes a magnetic deviation of 20 degrees?
If you think about it, if the local Earth's field is 1.0 in the $x$ direction, and you have a perturbing field in the $y$ direction, the vector sum can change by tens of degrees while the magnitude only changes a few percent.
Compare the magnitude $\sqrt{1 + a^2}$ with the angle $\arctan{a}$:
  a      magnitude    deviation (degs)
-----    ---------    ----------------
  0        1.00              0.0
 0.1       1.02             11.3
 0.2       1.04             16.7
 0.3       1.08             21.8
 0.4       1.12             26.6

I don't see any way that you can reliably use a magnetic strength inferred from calibrated data from a cellphone magnetometer to detect faulty compass headings reliably. It might work once in a while, but for most of the causes of unreliable readings, it wont be very helpful.
About cellphone magnetometer data calibration, and verification
If you are using uncalibrated data, you must calibrate it. If you believe you are using calibrated data then you can still use the equation below to get an idea how well calibrated it is.
You would have to degauss and calibrate your cellphone's magnetometer chip carefully before even starting to believe the raw data values!
Calibration, automatic or manually by yourself, assumes at a minimum that each of the three channels has a gain and offset that need to be handled. The circular motion we make with our phones to calibrate the magnetometer will match the three gains, but leave the absolute scale uncalibrated, since an electronic compass will only use the ratios.
If you look at the plots at the end, you can see that without calibration adding the three components in quadrature while doing a 3D rotation does not produce a constant magnitude, in fact it's way off. After a calibration, the magnitude is more constant, but the absolute value can not be calibrated this way. You'd need to find a better instrument to get the magnitude.
To do this, you could minimize $S$, the deviation of the amplitude from some constant value:
$$S = \sum_{j=1}^n \left(
\sqrt{
\left(a_x\left(ADC_{x,j}-b_x \right) \right)^2 + \left(a_y\left(ADC_{y,j}-b_y \right) \right)^2 + \left(a_z\left(ADC_{z,j}-b_z \right) \right)^2
} -B_0 \right)^2$$
You can't even look up the geomagnetic field to calibrate because local geomagnetic fields can vary quite a bit depending on what is inside the Earth locally. For more on that see all the answers to Is there a “submerged object” in Australia that causes a magnetic deviation of 20 degrees?

A more advanced calibration might assume non-orthoginality between the three axes, and so there would be a first order mixing between, making the calibration a 3x4 augmented matrix with a form similar to the one I describe in Why is the notation (R|RT) for “first apply translation then rotation”? where the 3x3 rotations there are gains here, and the 3 translations there are offsets here.

For the type of magnetoresistive magnetometers found in cellphones, see:

Physics SE: What is actually happening when a magnetoresistive magnetometer degausses itself?
Electronics SE: Why do compass chips in cellphones require frequent calibration?
Electronics SE: How is the degaussing feature in the HMC5883L 3-Axis Digital Compass chip correctly used?

From this answer:

1. Degauss...
From Wikipedia's Degaussing; Magnetic data storage media:

Erasure via degaussing may be accomplished in two ways: in AC erasure, the medium is degaussed by applying an alternating field that is reduced in amplitude over time from an initial high value (i.e., AC powered); in DC erasure, the medium is saturated by applying a unidirectional field (i.e., DC powered or by employing a permanent magnet). A degausser is a device that can generate a magnetic field for degaussing magnetic storage media.

2. Calibrate out the fixed magnetizations...
When I use the compass on my phone it instructs me to "calibrate" it first by doing a weird swirly pattern. Internally it continuously digitizes the three magnetometers (and possibly my phone's gyros) during the motion in order to find a best fit to a spherical rotation of a constant vector. It doesn't know if the vector comes from the Earth's field alone or has other external contributions (magnetized or ferromagnetic materials nearby) but it will calibrate out any fixed magnetizations that are in my phone - that rotate along with the magnetometer and add constant offsets.
A random Arduino illustration from ancient history:


TITLE: Is there a true parallel between Gibbs' phase rule and Euler's polyhedral formula?
QUESTION [17 upvotes]: Gibbs' phase rule states: $$F=C-P+2$$ where $F$ is number of degrees of freedom, $C$ is number of components, $P$ is number of phases.
Euler's polyhedral formula states: $$V+F-E=2$$  where $V$ is number of vertices, $F$ is number of faces, $E$ is number of edges.
It is easy to see that these formulas are similar. Is there a true parallel between them? Otherwise, what is the mathematical meaning of Gibbs' phase rule?

REPLY [3 votes]: Gibb's phase rule is much simpler than Euler's formula.
First of all, we're talking about a phase diagram which has $C + 2$ dimensions, where $C$ of the coordinates are chemical potentials for the $C$ many components, and the extra two are pressure and temperature, as hyportnex says.
Suppose there is a special submanifold of the phase diagram which lies at a co-existence junction between $P$ different phases. Then Gibb's phase rule just says that since $P$ is the codimension, the dimension of this submanifold, namely the number of degrees of freedom $F$, is the dimension minus the codimension, or
$$F = C + 2 -P.$$
It's equivalent to the rank-nullity theorem in linear algebra. This is a far simpler result compared to Euler's formula, which is a global property of graphs on the 2d sphere. Gibb's phase rule meanwhile is simply a local property in the phase diagram, which has different meaning at different points. It tells us nothing of the global structure.
If one were to invent a correspondence between them, it would be quite ad-hoc, since such a correspondence would have to say that there is something very special about temperature and pressure, ie. about the number 2. In topology 2 is very special, since it is the largest Euler characteristic among connected surfaces. If we included another tuning parameter, then the phase rule would read
$$F = C+3 - P,$$
and there is no connected surface of Euler characteristic 3, so nowhere to draw the graph that's supposed to be associated to each point of the phase diagram.


TITLE: How To Solve $\frac{1}{X}\bigg\lfloor-\frac{3}{2}+\frac{1}{2}\sqrt{8X+9}\bigg\rfloor=\frac{1}{N}$ over the integers.
QUESTION [0 upvotes]: Question: If $X$ and $N$ are positive numbers. How would I solve for $X$ in the following equation:
$$
\frac{1}{X}\bigg\lfloor-\frac{3}{2}+\frac{1}{2}\sqrt{8X+9}\bigg\rfloor=\frac{1}{N} \label{a}\tag{1}
$$
?

For example If $N=7$ then $X \in \{63,70,77\}.$ If $N=6$ then $X\in\{42,48,54\}.$ Careful with $N=4.$ The floor part of the LHS of $\ref{a}$ yields the sequence:
$$
0,1,1,1,2,2,2,2,3,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,5,\ldots;
$$
Here is a Wolfram Alpha "script" in the case $N=7$. You can change $7$ to another integer say $4$ etc..
Solve[Floor[-3/2 + (1/2) Sqrt[8 X + 9]]/X == 1/7, X, Integers]

REPLY [3 votes]: Multiply by $X$ on both sides to get $$\left\lfloor-\frac{3}{2}+\frac{1}{2}\sqrt{8X+9}\right\rfloor=\frac{X}{N}$$
This shows that $X$ must be a multiple of $N$ and that $$\frac{X}{N} \le -\frac{3}{2}+\frac{1}{2}\sqrt{8X+9} < \frac{X}{N}+1$$
Multiply by $2$, add $3$, and square it to get $$\left(\frac{2X}{N}+3\right)^2 \le 8X+9 < \left(\frac{2X}{N}+5\right)^2$$
Expanding it, there are two inequalities: $$\frac{4X^{2}}{N^{2}}+\left(\frac{12}{N}-8\right)X \le 0$$ $$\frac{4X^{2}}{N^{2}}+\left(\frac{20}{N}-8\right)X+16 > 0$$
Assuming that $X, N > 0$, the first inequality means that $$X\le2N^{2}-3N \tag 1$$ and the second one means that $N<\frac{9}{2}$ or $$X<\frac{2N^{2}-5N-N\sqrt{9-20N+4N^{2}}}{2} \tag 2$$ or $$X>\frac{2N^{2}-5N+N\sqrt{9-20N+4N^{2}}}{2} \tag 3$$
$(2)$ would never be true because for $N \ge 5$, the upper bound on $X$ would be less than $N$ and $X$ has to be a positive multiple of $N$.
If $N < \frac{9}{2}$ (i.e. is in $\{ 1, 2, 3, 4 \}$), then $X = kN$, where $k$ is an integer in $[1, 2N-3]$. Otherwise, $X = kN$, where $k$ is an integer in $$\bigg(\frac{2N-5+\sqrt{9-20N+4N^{2}}}{2}, 2N-3\bigg]$$
Because $2N-5 - $ (the lower bound) $\le 1$ for $N \ge 5$, this means that this simplifies to $k \in \{2N-5, 2N-4, 2N-3\} \to X \in \{N(2N-5), N(2N-4), N(2N-3)\}$.


TITLE: Level of detail in real analysis proofs?
QUESTION [1 upvotes]: I'm working through Stephen Abbott's wonderful Understanding Analysis in preparation for entering a math undergrad degree this fall. A personal note about me: Friends and family tell me I tend to be periphrastic; if there's a long-winded, inelegant way of explaining myself, I'll find it. As I work through Abbott's book, I wonder: Are all the steps I'm taking (even to solve simple problems near the beginning of the book) necessary, or is my brain just doing what it always does by finding the most round-about way to do things? So I'd like to have someone critique a simple proof to see if I'm doing something wrong, or if this really is the way things are done in real analysis.

Exercise 2.2.5. Let $\lfloor x\rfloor$ be the greatest integer less than or equal to x. Find $lim_{n\to \infty} a_n$ and supply proofs if $a_n=\lfloor \frac 1n \rfloor$.

In the preceeding chapter, Abbott has already shown that $lim_{n \to \infty} \frac 1n =0$, so we can take this as given. Then we note that since $n \lt (n+1)$ $\forall n \in \mathbb N$, we have $\frac 1n \gt \frac 1{n+1} \gt 0$,  $\forall n \in \mathbb N$. And since by inspection $a_n = 1$, we have
$$1\gt a_{n+1} \gt a_{n+2} \gt a_{n+3} \gt \cdots \gt0,$$
so that $a_n = 0$ for $ n \ge2$. Finally, since $|a_n-0|=0$ for $n \ge2$, we must have $|a_n - 0| \lt \epsilon$, $\forall \epsilon \gt 0$ and $n \ge2$. Therefore $\lim_{n \to \infty} a_n=0$.
Is this correct? Have I included any unnecessary steps? It just seems so pathologically nit-picky! And I feel the same way about most of the other exercises in the book. Thanks for your help!

REPLY [1 votes]: for all $n\ge 2$,
$$
0 < \frac{1}{n} < 1
$$
Thus, for all $n\ge 2$,
$$
\left\lfloor \frac{1}{n} \right\rfloor = 0
$$
Thus $\lim_{n\to \infty} a_n = 0$


TITLE: If $f(x,y)=9-x^2-y^2$ if $x^2+y^2\leq9$ and $f(x,y)=0$ if $x^2+y^2>9$ study what happens at $(3,0)$
QUESTION [3 upvotes]: If$$f(x,y)=\begin{cases}9-x^2-y^2&\text{if }x^2+y^2\leq9\\0&\text{if }x^2+y^2>9\end{cases}$$study the continuity and existence of partial derivative with respect to $y$ at point $(3,0)$.

The graph of the domain of $f$ is:

Continuity study at $(3,0)$:
$f(3,0)=9-3^2-0=0$, but I do not know how to find $$\lim_{(x,y)\to(3,0)}f(x,y).$$ I tried the following: $$\lim_{(x,y)\to(3,0)}f(x,y)=\left\{\begin{array}{l}\displaystyle\underset{C_1\colon x^2+y^2=9}{\lim_{(x,y)\to(3,0)}}f(x,y)=\underset{C_1\colon x^2+y^2=9}{\lim_{(x,y)\to(3,0)}}(9-(x^2+y^2))=9-9=0\\\displaystyle\underset{C_2\colon x^2+y^2\neq9}{\lim_{(x,y)\to(3,0)}}f(x,y)=\underset{C_2\colon x^2+y^2\neq9}{\lim_{(x,y)\to(3,0)}}\text{??}=\text{??????}\end{array}\right.$$ but then I realized that the "curve" $C_2$ is actually NOT a curve but a set of infinite points, as shown in the previous image.
Existence of partial derivative with respect to $y$ at $(3,0)$:
I know that I need to study whether $$\frac\partial{\partial y}f(3,0)=f'((3,0);(0,1))=f_y(3,0)=\lim_{h\to0}\frac{f((3,0)+h(0,1))-f(3,0)}{h}=\lim_{h\to0}\frac{f(3,h)}{h}$$ exists or not, but I am not able to even find that limit.
Any help? Thanks!!

REPLY [1 votes]: Regarding the partial derivative question, note that $f(3,y) = 0$ for all values of $y$. (The line $x=3$ touches the circle $x^2+y^2=9$ tangentially and is otherwise completely outside, where the function is identically $0$.) Thus, $\frac{\partial f}{\partial y}(3,0) = 0$.
Now, if $a^2+b^2>9$, $f$ is identically $0$ in a neighborhood of $(a,b)$ and so $\frac{\partial f}{\partial y}(a,b) = 0$. If $a^2+b^2<9$, then $\frac{\partial f}{\partial y}(a,b) = -2b$. What happens if $a^2+b^2=9$ but $b\ne 0$? Then $\frac{\partial f}{\partial y}(a,b)$ does not exist:
\begin{multline*}
\lim_{h\to 0+}\frac{f(a,b+h)-f(a,b)}h = 0, \quad\text{whereas}\\
\lim_{h\to 0-}\frac{f(a,b+h)-f(a,b)}h = -2b\ne 0.
\end{multline*}
Therefore, $\frac{\partial f}{\partial y}$ is not continuous at $(3,0)$, as it is not even defined at all points nearby. Perhaps the question wasn't asking about this; it's a bit ambiguous.


TITLE: Commutator of position operator and field in scalar QFT
QUESTION [0 upvotes]: Given an energy momentum tensor $T^{\mu \nu} = \partial^{\mu} \phi \partial^{\nu} \phi - \eta^{\mu \nu}\mathcal{L}$, the standard definition of the momentum operator is $P^{\mu} \equiv \int d^3x T^{\mu 0} = \int d^3 x (\partial^0 \phi \partial^{\nu} \phi - \eta^{0\nu} \mathcal{L})$. I am not able to verify the claim that $i[P^{\mu},\phi(x)]=\partial^{\mu}\phi$.
We usually assume that $[\phi(x), \pi(y)] = i \delta(x-y);$ I am not quite sure why we identify $\partial^0 \phi$ as $\pi(y)$ in this case. Further, $[P^{\mu},\phi(x)] = \int d^3 x \;(\pi (\partial^{\mu}\phi)\phi - \eta^{0\nu}\mathcal{L}\phi) - \phi \int d^3 x (\partial^0 \phi \partial^{\nu} \phi - \eta^{0\nu} \mathcal{L})$, and I can't seem to simplify this expression. Perhaps the commutation is to be carried out in the integrand, in which case, by commutation of $\phi$ with $\mathcal{L}$ and $\partial^{\mu}\phi$, one would instead get $[P^{\mu},\phi(x)]= \int d^3 x \; \partial^{\mu} \phi[\pi,\phi] = -i \partial^{\mu} \phi$, which is the desired relation. However, I do not see why, formally speaking, the commutation should be carried out in the integrand.
I would also appreciate a line or two providing the intuition behind $P^{\mu}$'s definition and how it agrees with to our notion of momentum in elementary QM.

REPLY [1 votes]: Just an outline:

$\partial^0\phi$ is the canonical momentum because that's defined as $$\pi\sim\frac{\delta S}{\delta \dot\phi}\,,$$ as in classical mechanics.
The definition of $P^\mu$ basically relies on Noether's theorem: The energy-momentum tensor is constructed to be the conserved current associated with spacetime translations (i.e. $\partial_\mu T^{\mu\nu}=0$ because translation leave the action invariant), and the conserved charge is obtained by a spatial integral of the $0$-component. (Commonly, you have a vector current and thus a scalar charge, but in this case, it's a two-tensore current and a vector charge.)
You have an expression $\left(\int \text{d}^3 x T^{\mu0}(x)\right)\phi(y) - \phi(y) \left(\int \text{d}^3 x T^{\mu0}(x)\right)$. (Note that it helps to be more explicit in your arguments -- this expression is not a function of $x$!) Now where elso would you "perform the commutator"  other than $\int \text{d}^3 x\, \left[T^{\mu0}(x),\phi(y)\right]$ ? (If you worry about well-definedness, given that there are delta functions involved, you would need to integrate against test functions. The result hold in the sense of operator-valued distributions.)


TITLE: Fourier transform on $\mathbb{R}^3$
QUESTION [4 upvotes]: I've been stuck on this one homework problem for nearly a day now, so I'd be really thankful for any pointers. The problem is to find
$$\int\int\int_{\mathbb{R}^3} \frac{1}{\mathbf{x}^2+1}e^{-2\pi i (x_1\zeta_1+x_2\zeta_2+x_3\zeta_3)}dx_1dx_2dx_3$$
where $\mathbf{x}\in \mathbb{R}^3$. I'm not sure how to go about this; I know that the Fourier transform of $1/(1+x^2)$ in $\mathbb{R}$ is $\pi e^{-2\pi |\zeta|}$, but I don't think that helps at all. I've tried changing it to spherical coordinates as well.
Also, if anyone could briefly explain how this relates to solving the equation $u(x)-\Delta u(x)=f(x)$, $x\in \mathbb{R}^3$ and $\Delta$ being the Laplacian operator, I'd be eternally grateful.

REPLY [4 votes]: Let's compute the Fourier Transform of the surface measure on a sphere of radius $r$. We will do this by integrating in slices.
The singular measure supported on the sphere is the limit of the volume measure on a thin sphere of thickness $\mathrm{d}r$ divided by $\mathrm{d}r$. When integrating a slice, the angle of intersection of the slice with the sphere must be taken into account. In the diagram below, it is shown that a surface of thickness $\mathrm{d}r$
intersecting a surface of thickness $\mathrm{d}x$ at an angle of $\theta$ has a cross sectional area of $\mathrm{d}x\,\mathrm{d}r\sec(\theta)$.
$\hspace{2cm}$
When integrating along the slice whose intersection with the sphere is a circle of radius $r\cos(\theta)$, the angle of intersection of the slice with the surface of the sphere is $\theta$. Thus, the $\sec(\theta)$ from the angle of the intersection is cancelled by the $\cos(\theta)$ from the radius of the circle. Therefore,
$$
\begin{align}
\int_{rS^2}e^{-2\pi i\,x\cdot\xi}\,\mathrm{d}x
&=\int_{-r}^r2\pi re^{-2\pi i\,t|\xi|}\mathrm{d}t\\
&=\frac{r}{-i|\xi|}\left(e^{-2\pi i\,r|\xi|}-e^{2\pi i\,r|\xi|}\right)\\
&=\frac{2r}{|\xi|}\sin(2\pi r|\xi|)\tag{1}
\end{align}
$$
Computing the Fourier Transform
To compute the Fourier transform of $\dfrac{1}{r^2+1}$, we integrate against $(1)$:
$$
\begin{align}
\int_0^\infty\frac{2r}{|\xi|}\frac{\sin(2\pi r|\xi|)}{r^2+1}\mathrm{d}r
&=\int_{-\infty}^\infty\frac{r}{|\xi|}\frac{\sin(2\pi r|\xi|)}{r^2+1}\mathrm{d}r\\
&=\frac{1}{|\xi|}\int_{-\infty}^\infty\frac{r\sin(r)\,\mathrm{d}r}{r^2+4\pi^2|\xi|^2}\\
&=\frac{1}{|\xi|}\Im\left(\int_{-\infty}^\infty\frac{re^{ir}\,\mathrm{d}r}{r^2+4\pi^2|\xi|^2}\right)\\
&=\frac{1}{|\xi|}\Im\left(\int_\gamma\frac{re^{ir}\,\mathrm{d}r}{r^2+4\pi^2|\xi|^2}\right)\\
&=\frac{1}{|\xi|}\Im\left(2\pi i\operatorname{Res}\left(\frac{re^{ir}}{r^2+4\pi^2|\xi|^2},2\pi i|\xi|\right)\right)\\
&=\frac{1}{|\xi|}\Im\left(2\pi i\frac{2\pi i|\xi|e^{-2\pi|\xi|}}{4\pi i|\xi|}\right)\\
&=\frac{\pi}{|\xi|}e^{-2\pi|\xi|}\tag{2}
\end{align}
$$
where $\gamma$ is the limit of the path on the real axis from $-M$ to $M$ followed by the semi-circle in the upper half-plane centered at $(0,0)$ from $M$ back to $-M$ as $M\to\infty$.
Therefore,
$$
\int_{\mathbb{R}^3}\frac{1}{|x|^2+1}e^{-2\pi i\,x\cdot\xi}\;\mathrm{d}x=\frac{\pi}{|\xi|}e^{-2\pi|\xi|}\tag{3}
$$

Relation to the Laplacian Equation
Taking the Fourier Transform of
$$
u(x)-\Delta u(x)=f(x)\tag{4}
$$
yields
$$
(1+4\pi^2|\xi|^2)\hat{u}(\xi)=\hat{f}(\xi)\tag{5}
$$
which becomes
$$
\hat{u}(\xi)=\dfrac{1}{1+4\pi^2|\xi|^2}\hat{f}(\xi)\tag{6}
$$
and taking the Inverse Fourier Transform yields
$$
\begin{align}
u(x)
&=\left(\dfrac{1}{1+4\pi^2|\xi|^2}\right)^\wedge(x)\ast f(x)\\
&=\frac{1}{4\pi|x|}e^{-|x|}\ast f(x)\tag{7}
\end{align}
$$
The convolution in $(7)$ is a Singular Integral.


TITLE: Soft question:Intuition for tangent space
QUESTION [2 upvotes]: I am trying to learn topology, from An introduction to manifolds of Loring W.Tu second edition to be precise, while I saw the definition of tangent space I don't think I understood what they are and what they mean, how would you explain the concept of tangent space in an informal manner.

REPLY [2 votes]: Below I give the notion as in Differential Geometry, other definitions of course exist:
For simplicity let us consider our manifold to be the surface of the unit sphere in $\mathbb{R}^3$, which of course may be described as: S = $\{ a \in \mathbb{R^3} : ||a|| = 1\}$
$v \in \mathbb{R}^3$ is a tangent vector of $S$ at $x \in S$ if there is a smooth curve, $\gamma:\mathbb{R} \rightarrow S$ s.t.

$\gamma(0) = x$
$\dot{\gamma}(0) = v $

The set of tangent vectors of $S$ at $x$, denoted $T_x(S)$ is given to be:
$$T_x(S) = \{\dot{\gamma}(0)| \gamma \textrm{ smooth,}\gamma(0) = x\}. $$
Say $x = (1,0,0)$  Then, intuitively, what would the tangent space be?
what will its dimension be?
The intuition we develop in 3 space will hold for $n$ space


TITLE: Inequality. $\frac{1}{16}(a+b+c+d)^3 \geq abc+bcd+cda+dab$
QUESTION [19 upvotes]: I want to prove the following inequality :

$$\frac{1}{16}(a+b+c+d)^3 \geq abc+bcd+cda+dab,  $$
  $a,b,c,d \in \mathbb{R}_{+} .$

In my book, at the answers chapter the author uses AM $\geq$ GM, but I haven't any idea how I can use that.
Thanks :)

REPLY [1 votes]: As noted by Zarrax, it suffices to show that
$$(a + b + c + d)^3 - 16(abc + bcd + cda + dab) = 4 \sum_{\mathrm{sym}}a^3 + 36 \sum_{\mathrm{sym}} a^2 b - 40 \sum_{\mathrm{sym}}abc$$
is nonnegative for all $a, b, c, d \ge 0$. Here I use the notation $\sum_{\mathrm{sym}}f(a,b ,c, d) := (1/4!) \sum_{\pi \in S_4} f(\pi(a), \pi(b), \pi(c), \pi(d))$ as $\pi$ ranges over all permutations of $\{a, b, c, d\}$.
But by AM-GM, $a^3 + b^3 + c^3 \ge 3 abc$ so that $\sum_{\mathrm{sym}}(a^3 + b^3 + c^3) \ge 3 \sum_{\mathrm{sym}}abc$ or just $\sum_{\mathrm{sym}} a^3 \ge \sum_{\mathrm{sym}} abc$. Similarly, AM-GM also gives $a^2 b + a^2 c + b^2 a + b^2 c + c^2 a + c^2 b \ge 6 abc$, so that $\sum_{\mathrm{sym}} a^2 b \ge \sum_{\mathrm{sym}} abc$. Thus
$$4 \sum_{\mathrm{sym}}a^3 + 36 \sum_{\mathrm{sym}} a^2 b - 40 \sum_{\mathrm{sym}}abc
= 4 \left(\sum_{\mathrm{sym}}a^3  - \sum_{\mathrm{sym}}abc\right) + 36 \left(\sum_{\mathrm{sym}} a^2 b - \sum_{\mathrm{sym}}abc\right) \ge 0.$$


TITLE: Rational roots to quadratic forms in 4 variables
QUESTION [2 upvotes]: Hi,
I am interested in the following question. Let $F(x_1, x_2, x_3, x_4)$ be a quadratic form in four variables with integer coefficients. Let $B > 0$ be a parameter. Define $N_1(F,B)$ to be the number of rational solutions to the equation $F(x_1, x_2, x_3, x_4) = 0$, such that $|x_i| \leq B$ for $i = 1,2,3,4$. I am looking for an upper bound of the form
$$\displaystyle N_1(F,B) \ll_\epsilon B^{\theta + \epsilon},$$
where the constant $\theta < 2$. Is there any such results known? One can assume that $F$ is absolutely irreducible and if necessary, assume that $F$ is non-singular.

REPLY [10 votes]: To rephrase Elkies's answer in elementary terms, here is an approach to derive an asymptotic formula for the number $N(T)$ of integer solutions to $x_1 x_3 - x_2 x_4 = 0$, with $x_1^2 + x_2^2 + x_3^2 + x_4^2 \leq T^2$.
Let $A = \begin{pmatrix} x_1 & x_2 \\ x_3 & x_4 \end{pmatrix}$. Then the above equation is $\det A = 0$. If $\det A = 0$ for an integer matrix $A$, then there exists an integer vector $v$ with $A v = 0$. Now given an integer vector $v$, let $N_v(T)$ denote the number of integer matrices $A$ of norm at most $T$ such that $A v = 0$. This is a linear problem, one is counting the number of integer points in the two dimensional subspace $$R_v = \{ A \in M_2(\mathbf{R}) \mid Av = 0 \}.$$
Now it is easy to see that the integer lattice $M_2(\mathbf{Z})$ intersects $R_v$ in a lattice of covolume $\|v\|^2$. Therefore, $N_v(T)$ is asymptotic to $\pi T^2/\|v\|^2$, and so,
$$N(T) \sim \sum_{\stackrel{ v \in \mathbf{Z}^2}{\|v \| \le T}} N_v(T) \sim \sum_{\stackrel{ v \in \mathbf{Z}^2}{\|v \| \le T}} \frac{\pi T^2}{\|v\|^2} \sim \pi T^2 \log T.$$
(One still has to justify why the correct place to cut off the sum over $v$ is around $\|v \| = T$, and also to justify the interchange of limits. This is done e.g. in the following paper:
Katznelson, Y. R. Singular matrices and a uniform bound for congruence groups of $\mathrm{SL}_n(\mathbf{Z})$. Duke Math. J. 69 (1993), no. 1, 121–136.)


text:
In this section we constrain ourselves to the asymmetric matrix factorization problem and analyze the gradient descent algorithm with random initialization.
Our analysis is inspired by the auto-balancing properties presented in Section~\ref{sec:conserved}. We extend these properties from gradient flow to gradient descent with positive step size.

Formally, we study the following non-convex optimization problem:
\begin{equation} \label{eqn:mf}
\min_{\mat{U} \in \R^{d_1\times r}, \mat{V} \in \R^{d_2\times r}} f(\mat{U}, \mat{V}) = \frac12 \norm{\mat{U}\mat{V}^\top - \mat{M}^*}_F^2,
\end{equation}
where $\mat M^* \in \R^{d_1\times d_2}$ has rank $r$.
Note that we do not have any explicit regularization in \eqref{eqn:mf}.
The gradient descent dynamics for \eqref{eqn:mf} have the following form:
\begin{equation} \label{eqn:mf-gd-dynamics}
\mat U_{t+1} = \mat U_t - \eta_t (\mat U_t \mat V_t^\top - \mat M^*) \mat V_t, \qquad
\mat V_{t+1} = \mat V_t - \eta_t (\mat U_t \mat V_t^\top - \mat M^*)^\top \mat U_t.
\end{equation}

\subsection{The General Rank-$r$ Case}

First we consider the general case of $r\ge1$.
Our main theorem below says that if we use a random small initialization $(\mat U_0, \mat V_0)$, and set step sizes $\eta_t$ to be appropriately small, then gradient descent \eqref{eqn:mf-gd-dynamics} will converge to a solution close to the global minimum of \eqref{eqn:mf}.
To our knowledge, this is the first result showing that gradient descent with random initialization directly solves the un-regularized asymmetric matrix factorization problem~\eqref{eqn:mf}.

\begin{thm}\label{thm:mf-main}
	Let $0<\epsilon < \norm{\mat M^*}_F$.
	Suppose we initialize the entries in $\mat U_0$ and $\mat V_0$ i.i.d. from $\cN(0, \frac{\epsilon}{\poly(d)})$ ($d = \max\{d_1, d_2\}$), and run  \eqref{eqn:mf-gd-dynamics} with step sizes $\eta_t = \frac{\sqrt{\epsilon/r}}{100(t+1) \norm{\mat M^*}_F^{3/2}}$ ($t=0,1,\ldots$).\footnote{The dependency of $\eta_t$ on $t$ can be $\eta_t = \Theta\left( t^{-(1/2+\delta)} \right)$ for any constant $\delta \in (0, 1/2]$.}
	Then with high probability over the initialization, $\lim_{t\to\infty}(\mat U_t, \mat V_t) = (\bar{\mat U}, \bar{\mat V})$ exists and satisfies $\norm{\bar{\mat U} \bar{\mat V}^\top - \mat M^*}_F \le \epsilon$.
\end{thm}

\paragraph{Proof sketch of Theorem~\ref{thm:mf-main}.}
	First let's imagine that we are using infinitesimal step size in GD. Then according to Theorem~\ref{thm:conserved-linear} (viewing problem~\eqref{eqn:mf} as learning a two-layer linear network where the inputs are all the standard unit vectors in $\R^{d_2}$), we know that $\mat U^\top \mat U - \mat V^\top \mat V$ will stay invariant throughout the algorithm.
	Hence when $\mat U$ and $\mat V$ are initialized to be small, $\mat U^\top \mat U - \mat V^\top \mat V$ will stay small forever.
	Combined with the fact that the objective $f(\mat U, \mat V)$ is decreasing over time (which means $\mat U \mat V^\top$ cannot be too far from $\mat M^*$), we can show that $\mat U$ and $\mat V$ will always stay bounded.

	Now we are using positive step sizes $\eta_t$, so we no longer have the invariance of $\mat U^\top \mat U - \mat V^\top \mat V$.
	Nevertheless, by a careful analysis of the updates, we can still prove that $\mat U_t^\top \mat U_t - \mat V_t^\top \mat V_t$ is small, the objective $f(\mat U_t, \mat V_t)$ decreases, and $\mat U_t$ and $\mat V_t$ stay bounded.
	Formally, we have the following lemma:
	\begin{lem} \label{lem:mf-balance}
		With high probability over the initialization $(\mat U_0, \mat V_0)$, for all $t$ we have:
		\begin{enumerate}[(i)]
			\item Balancedness: $\norm{\mat U_t^\top \mat U_t - \mat V_t^\top \mat V_t}_F \le \epsilon$;
			\item Decreasing objective: $f(\mat U_{t}, \mat V_{t}) \le f(\mat U_{t-1}, \mat V_{t-1}) \le \cdots \le f(\mat U_{0}, \mat V_{0}) \le 2\norm{\mat M^*}_F^2$;
			\item Boundedness: $\norm{\mat U_{t}}_F^2 \le 5\sqrt{r} \norm{\mat M^*}_F, \norm{\mat V_t}_F^2 \le  5\sqrt{r} \norm{\mat M^*}_F$.
		\end{enumerate}
	\end{lem}

	Now that we know the GD algorithm automatically constrains $(\mat U_t, \mat V_t)$ in a bounded region, we can use the smoothness of $f$ in this region and a standard analysis of GD to show that $(\mat U_t, \mat V_t)$ converges to a stationary point $(\bar{\mat U}, \bar{\mat V})$ of $f$ (Lemma~\ref{lem:mf-convergence}).
	Furthermore, using the results of \citep{lee2016gradient, panageas2016gradient} we know that $(\bar{\mat U}, \bar{\mat V})$ is almost surely not a strict saddle point.
	Then the following lemma implies that $(\bar{\mat U}, \bar{\mat V})$ has to be close to a global optimum since we know $\norm{\bar{\mat U}^\top \bar{\mat U} - \bar{\mat V}^\top \bar{\mat V}}_F \le \epsilon$ from Lemma~\ref{lem:mf-balance} (i). This would complete the proof of Theorem~\ref{thm:mf-main}.

\begin{lem} \label{lem:mf-strict-saddle}
	Suppose $(\mat{U}, \mat{V})$ is a stationary point of $f$ such that $\norm{\mat U^\top \mat U - \mat V^\top \mat V}_F \le \epsilon$.
	Then either $\norm{\mat U \mat V^\top - \mat M^*}_F \le \epsilon$, or $(\mat{U}, \mat{V})$ is a strict saddle point of $f$.
\end{lem}

The full proof of Theorem~\ref{thm:mf-main} and the proofs of Lemmas~\ref{lem:mf-balance} and \ref{lem:mf-strict-saddle} are given in Appendix~\ref{sec:proof-mf}.

\subsection{The Rank-$1$ Case}

We have shown in Theorem~\ref{thm:mf-main} that GD with small and diminishing step sizes converges to a global minimum for matrix factorization.
Empirically, it is observed that a constant step size $\eta_t \equiv \eta$ is enough for GD to converge quickly to global minimum.

Therefore,
some natural questions are how to prove convergence of GD with a constant step size, how fast it converges, and how the discretization affects the invariance we derived in Section~\ref{sec:conserved}.

While these questions remain challenging for the general rank-$r$ matrix factorization, we resolve them for the case of $r=1$.

Our main finding is that with constant step size, the norms of two layers are always within a constant factor of each other (although we may no longer have the stronger balancedness property as in Lemma~\ref{lem:mf-balance}), and
 we utilize this property to prove the \emph{linear convergence} of GD to a global minimum.

When $r=1$, the asymmetric matrix factorization problem and its GD dynamics become
$$
\min_{\vect{u} \in \mathbb{R}^{d_1}, \vect{v} \in \mathbb{R}^{d_2}} \frac12 \norm{\vect{u}\vect{v}^\top - \mat{M}^*}_F^2
$$
and
\begin{align*}
\vect{u}_{t+1} = \vect{u}_t - \eta (\vect{u}_t\vect{v}_t^\top - \mat{M}^*)\vect{v}_t, \qquad
\vect{v}_{t+1} = \vect{v}_t - \eta\left(\vect{v}_t\vect{u}_t^\top - \mat{M}^{*\top} \right)\vect{u}_t.
\end{align*}
Here we assume $\mat{M}^*$ has rank $1$, i.e., it can be factorized as $\mat{M}^* = \sigma_1 \vect{u}^*\vect{v}^{*\top}$ where $\vect{u}^*$ and $\vect{v}^*$ are unit vectors and $\sigma_1>0$.

Our main theoretical result is the following.
\begin{thm}[Approximate balancedness and linear convergence of GD for rank-$1$ matrix factorization]
	\label{thm:rank_1}
	Suppose $\vect{u}_0 \sim \cN(\vect 0,\delta\mat{I})$, $\vect{v}_0 \sim \cN(\vect 0,\delta \mat I)$ with $\delta = c_{init} \sqrt{\frac{\sigma_1}{d}}  $ ($d = \max\{d_1, d_2\}$)
	 for some sufficiently small constant $c_{init} >0$,

	 and $\eta = \frac{c_{step}}{\sigma_1}$ for some sufficiently small constant $ c_{step} >0$.
	Then with constant probability over the initialization, for all $t$ we have $c_0\le \frac{\abs{\vect{u}_t^\top \vect u^*}}{\abs{\vect{v}_t^\top \vect{v}^*}}\le C_0$ for some universal constants $ c_0,C_0>0$.
	Furthermore, for any $0<\epsilon< 1$, after $t = O\left( \log\frac{d}{\epsilon} \right)$ iterations, we have $\norm{\vect{u}_t\vect{v}_t^\top - \mat{M}^*}_F \le \epsilon \sigma_1$.
\end{thm}
Theorem~\ref{thm:rank_1} shows for $\vect{u}_t$ and $\vect{v}_t$, their strengths in the signal space, $\abs{\vect{u}_t^\top \vect{u}^*}$ and $\abs{\vect{v}_t^\top \vect{v}^*}$, are of the same order.

This approximate balancedness helps us prove the linear convergence of GD.

We refer readers to Appendix~\ref{sec:proof-rank-1} for the proof of Theorem~\ref{thm:rank_1}.

config: arxiv


TITLE: What does "Find all functions $A \rightarrow B$" mean?
QUESTION [0 upvotes]: I keep coming across questions written in this format and I don't understand this notation. An example of a question is: Find all functions $f : \{1,2,3,\ldots\} \rightarrow \{1,2,3,\ldots\}$, such that for all $n = 1, 2, 3,\ldots$ the sum $f(1) + f(2) + ... + f(n)$ is equal to a perfect cube less than or equal to $n^3$.
Another example here: How many functions $g$ can be defined from set $A = \{0, 1,\ldots, 2^n -1, 2^n\}$ to set $B = \{0, \ldots , n\}$ such that $g(2^x) = x$ for all $x \in B$?
I don't need either questions solving but the notation explained.

REPLY [0 votes]: $f:A\to B$ means $f$ is a function from $A$ into $B$ or onto $B.$
Presumably $\{1,2,3,..\}$ means $\Bbb N,$  the set of positive integers. So the problem reads: Find all functions from $\Bbb N$ to $\Bbb N$ such that ... (etc.).
n^3 means $n^3$.
In the 2nd problem $A$ is set of non-negative integers that do not exceed $2^n$ and $B$ is the set of non-negative integers that do not exceed $n.$
Click on the "?" on the top bar (far right), choose Help Center, and click on "How Do I Format Mathematics Here?"


TITLE: In a metric space, compactness implies completness
QUESTION [6 upvotes]: Proposition Let $(M,d)$ be a metric space. If $K\subset M$ is compact, then $K$ is complete.

Proof Let $\{x_n\}_{n=1}^\infty \subset K$ be a Cauchy sequence, then
$$ \forall \varepsilon > 0 \quad \exists n_0 \in \mathbb N \quad \forall m,n\geq n_0 \quad d(x_n,x_m) < \varepsilon.  $$
$(\text{Step } 1)$ Since $K$ is compact, $\{x_n\}_{n=1}^\infty$ has an accumulation point $x^*\in K$ (already proved for every metric space). Let's see that $\lim_{n\to\infty} x_n = x^*$.
$(\text{Step }  2)$ Since $x^*$ is an accumulation point $$\forall k\in \mathbb N \quad \exists x_{n_k} \quad\text{s.t.}\quad d(x_{n_k}, x^*) <\frac{1}{k} $$
$(\text{Step }  3)$ Let $\varepsilon > 0$, then $\exists k_0 \quad n_{k_0} \geq n_0 \quad d(x_{n_{k_0}} x^*) < \varepsilon $. Now if $n \geq n_0$, then
$$ d(x_n,x*) \leq d(x_n, x_{n_{k_0}}) + d(x_{n_{k_0}}, x*) \leq \varepsilon + \varepsilon = 2\varepsilon $$
so every Cauchy sequence converges and $K$ is complete.
Question Is this proof correct? I can't understand steps $(2)$ and $(3)$ (why uses $\frac{1}{k}$?).
Thanks in advance.

Edit Is this proof correct?
Let $\{x_n\}_{n=1}^\infty \subset K$ be a Cauchy sequence, by definition $\forall
\varepsilon >0 \;\, \exists n_0\in \mathbb N \;\, \forall m,n \geq n_0 \;\, d(x_n,
x_m) < \varepsilon$. Since $K$ is compact, the sequence has an accumulation point  $x^*\in K$ (already proved). Let's see that $\lim_{n\to\infty}x_n = x^*$: since $x^*$ is an accumulation point, then exists a subsequence
    $\{x_{n_k}\}_{k=1}^{\infty}\subset \{x_{n}\}_{n=1}^{\infty}$ that converges to $x^*$, in other words $\forall
 \varepsilon > 0 \;\, \exists k_0\in\mathbb N \;\, \forall k \geq k_0 \;\,  d(x_{n_{k}}, x^*) < \varepsilon$. Because of the triangular property $d(x_n,x^*) \leq d(x_n, x_{n_{k}}) + d(x_{n_{k}}, x^*) \leq 2\varepsilon$, so every Cauchy sequence converges and $K$ is complete.

REPLY [1 votes]: In (Step 2) you are essentially constructing a subsequence of $\{ x_n \}_{n=1}^\infty$ which converges to the accumulation point $x^*$ of $\{ x_n : n \in \mathbb{N} \}$.  I say essentially because you are not ensuring that $n_{k+1} > n_k$, but the basic idea is there.  The use of $\frac 1k$ is not overly important, but you do want some sequence of positive real numbers converging to $0$.
(Step 3) is essentially a proof of the following: Every Cauchy sequence in a metric space with a convergent subsequence is convergent (to the same limit).


TITLE: Binnig's fractal evolution applied to multiple universes?
QUESTION [0 upvotes]: Gerd Binnig, Nobel laureate in physics in 1986, proposed in his article "The fractal structure of evolution" 1 that everything in the universe, including its laws, had changed and became what we have got today through a process which mixes some concepts from darwinian evolution and fractal cosmology. I had some questions about this article and mr. Binnig ideas that I would like to clarify:

In that article, Binnig says that everything in the universe has resulted from an evolutionary process, including the laws of nature. But does this apply even to the most fundamental laws of nature? Would even the fundamental laws be subject to change in his theory of evolution applied to the entire universe? Or, on the contrary, only low-energy/effective laws could change?

Binnig describes his theory as closely related to Mandelbrot's fractal geometry. There are some cosmological theories that are also related to this, like Andrei Linde's cosmological inflation models. In fact, he seems to cite one of Andrei Linde's articles on inflationary cosmology which mixes fractals with the multiverse hypothesis 2 . Linde's models are closely related to the multiverse hypothesis, since they predict the existence of multiple universes. Since he cited Linde's models about multiple universes, was Gerd Binnig considering the possibility that multiple universes could exist? And if that was the case, would all these universes be also subject to change in his cosmological evolutionary process?

REPLY [0 votes]: There is probably good reason the paper is not widely cited. Basically it is conflating "fractal" with "hierarchical": systems on one level interact and produce systems on a higher level (e.g. particles make atoms that make molecules and so on), but fractals are scale-free: dynamics or appearance on one scale should be similar to other scales. This is not true in most physics (molecules behave very different from electrons).
It also makes a very weak case for evolution of the laws of nature: Linde's scenario makes an explicit evolutionary model, but it requires a very particular underlying physics that is not assumed to be evolved. So your first question is, in the paper, only low energy physics is evolving. Similarly, Wolfram's recent speculative model of physics has some basic string rewriting rules but could in principle allow for evolution-like behaviour of everything else in the world-graph. Generally, evolution does require some background assumptions (like time-irreversibility) that are non-trivial.
Linde's evolving universe model is separate from his chaotic inflation model (where I think you do get a proper fractal large-scale multiverse), but both do produce a multiverse in the sense that you get isolated worlds that evolve independently of each other once they exist. But what Binnig thought is hard to guess.


TITLE: In ZF, how would the structure of the cardinal numbers change by adopting this definition of cardinality?
QUESTION [10 upvotes]: In ZFC, a good way of ordering sets by cardinality is by leveraging the notion of an injection. We define: $$X \lesssim Y \leftrightarrow \mbox{ there exists an injection } X \rightarrow Y.$$
Alternatively, we can leverage the notion of a partial surjection, by which I mean a partial function that hits every point of its codomain at least once.
$$Y \succsim X \leftrightarrow \mbox{ there exists a partial surjection } Y \rightarrow X.$$
Now in ZFC, these approaches are equivalent, in the sense that $$X \lesssim Y \iff Y \succsim X.$$
But if we just consider ZF (that is, we drop choice) then the equivalence breaks down. However, we've still got the forward implication, because the converse of an injection is always a partial surjection.
A specific question. Define that two sets are weakly equipotent iff $X \succsim Y$ and $Y \succsim X$. Question: does weak equipotence imply genuine equipotence? I'm guessing "no."
A general question: In broad terms, how would the structure of the cardinal numbers in ZF be altered by adopting $\succsim$ rather than $\lesssim$ as the fundamental order relation, and taking equality of cardinal numbers to correspond to weak equipotence of sets? I'm guessing this would hide a lot of the (usually very complicated) structure of the cardinal numbers in ZF.
Remark. The order symbols can be written \lesssim and \succsim.

REPLY [4 votes]: The order which you define is commonly denoted by $\leq^*$, and I will use that notation in my answer as well.
As Andres wrote in his excellent answer, without the axiom of choice not much is provable about $\leq^*$. We know that if $\leq^*$ is antisymmetric (on cardinals) then there are no Dedekind-finite sets. We also know that if it is a total ordering then the axiom of choice holds.
We don't know a whole lot more other than that. Certain choice principles such as the partition principle (which essentially states $\leq=\leq^*$) imply the antisymmetry of $\leq^*$.
Specific counterexamples can be found when Dedekind-finite sets exist, for example, one can have a Dedekind-finite set $A$ such that $A<A+A\leq^*A$, so trivially $A\leq^*A+A$ but because the set is Dedekind-finite we have $A\nsim A+A$.
Beyond that, one can show the following statement:

Theorem. Suppose that $V$ is a model of $\sf ZFC$. For every set $A$ there exists a symmetric extension of $V$ such that $\mathcal P(A)$ can be embedded into the cardinals ordered by $\leq^*$ and $\leq^*$. Moreover, one can preserve $\sf DC_\kappa$ for an arbitrary $\kappa$ while doing so.

One can extend this and show the even weirder statement is true:

Theorem. Suppose that $V$ is a model of $\sf ZFC$, then there is a class-symmetric extension such that $(\mathcal P(\sf Ord),\subseteq)$ can be embedded into $\leq$ and $\leq^*$, while preserving $\sf DC_\kappa$. If $V$ satisfies global choice then $V$ itself embeds into the cardinals as well.

One interesting consequence from these theorems is that $\sf DC_\kappa$ is completely orthogonal to any chaotic behavior in $\leq^*$ and $\leq$. Another interesting conclusion is that one can have a decreasing chain of cardinals of any ordinal length (although not of length $\sf Ord$) alongside $\sf DC_\kappa$.


text:
\begin{document}
\publicationdetails{23}{2021}{1}{7}{6613}
\maketitle
\begin{abstract}
\noindent
The \textit{forbidden number} $\operatorname{forb}(m,F)$, which denotes the maximum number of unique columns in an $m$-rowed $(0,1)$-matrix with no submatrix that is a row and column permutation of $F$, has been widely studied in extremal set theory. Recently, this function was extended to $r$-matrices, whose entries lie in $\{0,1,\dots,r-1\}$. The combinatorics of the generalized forbidden number is less well-studied. In this paper, we provide exact bounds for many $(0,1)$-matrices $F$, including all $2$-rowed matrices when $r > 3$. We also prove a stability result for the $2\times 2$ identity matrix. Along the way, we expose some interesting qualitative differences between the cases $r=2$, $r = 3$, and $r > 3$.
\end{abstract}

\section{Introduction}
We call a matrix \emph{simple} if it has no repeated columns. Every set system (or simple hypergraph) corresponds to a simple $(0,1)$-matrix via its element-set incidence matrix, and such matrices provide a convenient language for extremal set theory. We generalize this situation to $r$-\emph{matrices}, which have entries in $\{0,1,\ldots, r-1\}$. Such matrices can be thought of as $r$-coloured set systems or as representations of collections of functions from a given finite set into $\{0,1,\dots,r-1\}$.

For two  matrices $F$ and $A$, we say that $F$ is a \textit{configuration} of $A$, denoted $F \prec A$, if $A$ contains a submatrix which is a row and column permutation of $F$. If $F\nprec A$, we say that $A$ \textit{avoids} $F$. Configurations of simple $(0,1)$-matrices correspond to traces of set systems or hypergraphs. For a given finite collection $\mathcal F$ of matrices, we denote by $\Avoid(m,r,{\mathcal F})$ the collection of $m$-rowed, simple $r$-matrices that avoid every matrix $F \in \mathcal F$. We let $\lvert A \rvert$ denote the number of columns of $A$. The main extremal function in the study of forbidden configurations is
\[
    \forb(m,r,{\mathcal F})=\max\{|A| : A \in \Avoid(m,r,{\mathcal F})\}.
\]
When $r=2$ we usually write $\forb(m,{\mathcal F})$ in place of $\forb(m,2,{\mathcal F})$. We also use $\forb(m,r,F)$ instead of the more cumbersome $\forb(m,r,\{F\})$. We will use several simple properties of this function. For example, if $F \prec F'$ then $\forb(m,r,F) \leq \forb(m,r,F')$. Also, we let $F^c$ denote the \textit{complement} of the $(0,1)$-matrix $F$, where each 0 is replaced by a 1 and vice versa; then $\forb(m,r,F) = \forb(m,r,F^c)$.

The foundational result in the theory of forbidden configurations is Sauer's theorem (proven in \cite{Sauer}, also by Perles and Shelah \cite{Shelah} and Vapnik and Chervonenkis \cite{VC}). Let $K_k$ denote the complete $k\times 2^k$ simple $(0,1)$-configuration (corresponding to the power set of a $k$-element set).
\begin{theorem}\label{Sauer's Thm} For every positive integer $m$,
\[
\forb(m,K_k) = \binom{m}{k-1} + \binom{m}{k-2} + \cdots + \binom{m}{1} + \binom{m}{0}.
\]
\end{theorem}

Alon \cite{ALON} gave a generalization for complete $r$-matrices, but the forbidden number is exponential when $r > 2$. This is a special case of a more general phenomenon proved by F\"uredi and Sali \cite{FS}.

\begin{theorem}
Let ${\mathcal F}$ be a family of $r$-matrices. If for every pair $i,j\in\{0,1,\dots,r-1\}$ there is an $(i,j)$-matrix in ${\mathcal F}$, then $\forb(m,r,{\mathcal F}) = O(m^k)$ for some positive integer $k$. If ${\mathcal F}$ has no $(i,j)$-matrix for some pair $i,j \in \{0,1,\dots,r-1\}$, then $\forb(m,r,{\mathcal F}) = \Omega(2^m)$.
\end{theorem}

Extensive investigations have been undertaken for forbidden configurations of simple $(0,1)$-matrices; see, for example, the excellent dynamic survey of Anstee \cite{survey}. On the other hand, the more general case of $r$-matrices is not so well-explored. Previous papers mainly focus on providing bounds on the forbidden number for special classes of sets in the polynomial case \cite{ansteelu,ELLIS202024}. In this paper, we dive into exponential forbidden numbers and provide exact bounds when $(0,1)$-configurations of $r$-matrices are forbidden. This is similar in flavour to a recent paper of F\"uredi, Kostochka, and Luo \cite{furedi-exponential}, which proves several minimum-degree conditions that guarantee cycles in hypergraphs; by dropping the assumption of uniformity, their bounds jump from polynomial to exponential.

The structure of the paper is as follows. \cref{sec:general-bounds} provides a method to transfer bounds for $r=2$ to larger values of $r$.  The following three sections calculate forbidden numbers of specific classes of matrices. We obtain exact results when $r>3$ and bounds for $r=3$ that differ from the forbidden number by an additive constant. We also prove a stability result for the identity configuration. Our work culminates in \cref{sec:two-rows}, which provides exact forbidden numbers for all two-rowed $(0,1)$-configurations for every $r>3$ and a large class of two-rowed $(0,1)$ configurations when $r=3$. The main tool in both cases a reduction lemma. Finally, \cref{sec:three-rows} applies the method of \cref{sec:general-bounds} to obtain a nearly complete classification of $(0,1)$-configurations of size $3\times 2$ and $3 \times 3$.

\section{General bounds}\label{sec:general-bounds}

For a given configuration $A$, let $\bar{A}$ denote its underlying simple configuration. If $A$ has $m$ columns and $S \subseteq [m]$, then we let $A\vert_S$ be the restriction of $A$ to the rows with indices in $S$. By convention, we set $\forb(0,F) = 1$ for all $F$. In general, if $F$ has $t$ rows, then $\forb(k,F) = 2^k$ when $0 \leq k < t$.

\begin{lemma}\label{thm:upper-01-bound}
If $F$ is a $(0,1)$-matrix and $r \geq 3$, then
\begin{equation}\label{eqn:upper-01-bound}
\forb(m,r,F) \leq \sum_{k=0}^m \binom{m}{k}(r-2)^{m-k}\forb(k,F).
\end{equation}
\end{lemma}
\begin{proof}
Let $A \in \Avoid(m,r,F)$, and let $X$ be a $k$-element subset of the rows. Consider the matrix $C$ obtained by taking all columns of $A$ that have 0's and 1's in exactly the rows in $X$, and let $C' = \overline{C\vert_X}$. We know that $\lvert C' \rvert \leq \forb(k,F)$. Each column in $C'$ appears with multiplicity at most $(r-2)^{m-k}$ in $C\vert_X$, so $\lvert C \rvert \leq (r-2)^{m-k}\forb(k,F)$. To finish the proof, we sum over all subsets of the rows.
\end{proof}

The bound given by this lemma may be quite bad, especially if $F$ is not simple. However, for simple matrices, we have the following lower bound.

\begin{lemma}\label{thm:lower-01-bound}
Let $F$ be a simple $(0,1)$-matrix with $n$ rows and fix $r \geq 3$. Suppose that $(A_k)_{k=1}^\infty$ is a sequence of $(0,1)$-matrices that avoids $F$, where $A_k$ has $k$ rows, such that $\overline{A_k\vert_S} \subseteq A_{n}$ for every $k \geq n$ and $S \in \binom{[k]}{n}$. If we set $\lvert A_0 \rvert = 1$, then
\begin{equation}
    \forb(m,r,F) \geq \sum_{k=0}^m \binom{m}{k}(r-2)^{m-k} \lvert A_k\rvert.
\end{equation}
\end{lemma}
\begin{proof}
We construct a configuration that avoids $F$ as follows. Let $k \in [m]$. For each $k$-set $X$ of rows, we choose the $(r-2)^{m-k}$ columns that contain a copy of $A_k$ in the rows of $X$ and have elements of $\{2,\dots,r-1\}$ in every other position. Let $A$ be the configuration that contains all such columns. If $F \prec A$, then $F \prec A\vert_{S}$ for some $n$-set of rows $S$. But every column in $A\vert_S$ appears in $A_n$, so $F \prec A_n$, a contradiction.
\end{proof}

The condition that $F$ is simple is absolutely essential. For simple matrices, however, this lemma can easily extend bounds from the classical case to the generalized one. In particular, combining \cref{thm:upper-01-bound,thm:lower-01-bound} proves the following.

\begin{lemma}\label{thm:01-equal}
Let $F$ be a simple $n$-rowed $(0,1)$-matrix. If there exists a sequence $(A_k)_{k=1}^\infty$ of $(0,1)$-matrices, each of which avoids $F$, such that\vspace{-1.3ex}
\begin{itemize}
    \setlength{\itemsep}{1pt}
    \setlength{\parskip}{0pt}
    \setlength{\parsep}{0pt}
    \item[\raisebox{1pt}{$\circ$}] $A_k$ has $k$ rows,\vspace{0.1em}
    \item[\raisebox{1pt}{$\circ$}] $\lvert A_k\rvert = \forb(k,F)$, and\vspace{0.2em}
    \item[\raisebox{1pt}{$\circ$}] $\overline{A_k|_S}$ is contained in $A_n$ for every $k\geq n$ and $n$-set $S \subseteq [k]$, then
\end{itemize}
\begin{equation}
    \forb(m,r,F) = \sum_{k=0}^m \binom{m}{k}(r-2)^{m-k}\forb(k,F).
\end{equation}
\end{lemma}

\section{Complete configurations}\label{sec:complete-configurations}

\begin{proposition}\label{thm:complete-config}
We have $\forb(m,r,K_k) = \sum_{i=0}^{k-1} \binom{m}{i} (r-1)^{m-i}$.
If $(r-1)^{m-k} \geq p-1$, then $\forb(m,r,p\cdot K_k) = \sum_{i=0}^{k-1}\binom{m}{i}(r-1)^{m-i} + (p-1)\binom{m}{k}$.
\end{proposition}
\begin{proof}
We first prove that $\forb(m,r,K_k) = \sum_{i=0}^{k-1}\binom{m}{i}(r-1)^{m-i}$. Let $A_n$ denote the $n$-rowed configuration that contains every column with at most $k-1$ zeros. Then $(A_n)$ satisfies the conditions of \cref{thm:01-equal}, so \cref{Sauer's Thm} implies that
\begin{align*}
    \forb(m,r,K_k)
    &= \sum_{n=0}^{m} \binom{m}{n} (r-2)^{m-n} \sum_{i=0}^{k-1} \binom{n}{i}\\
    &= \sum_{i=0}^{k-1} \binom{m}{i} \sum_{n=0}^m \binom{m-i}{n-i} (r-2)^{m-n}\\
    &= \sum_{i=0}^{k-1} \binom{m}{i}(r-1)^{m-i}.
\end{align*}

Now we prove the forbidden number for all $p$. The configuration that contains every column with at most $k-1$ zeros avoids $K_k$. If $(r-1)^{m-k} \geq p-1$, for each $k$-set of rows, we may append $p-1$ columns to this matrix that have zeros in that $k$-set and nowhere else. The resulting configuration avoids $p\cdot K_k$ and has $\sum_{i=0}^{k-1}\binom{m}{i}(r-1)^{m-i} + (p-1)\binom{m}{k}$ columns.

Now suppose that $A \in \Avoid(m,r,p\cdot K_k)$. For each $k$-set $X$ of rows, there is a column of $K_k$ that appears at most $p-1$ times in $A\vert_X$. Let $A'$ be the configuration obtained by deleting the corresponding columns of $A$ for all $k$-sets. Since $K_k$ is symmetric, no row-permutation of $K_k$ is a subset of $A'\vert_X$, so $K_k \nprec A'\vert_X$ for every $k$-set $X$. Therefore $K_k \nprec A'$, which implies that
\[
    \lvert A\rvert
    \leq \lvert A'\rvert + (p-1)\binom{m}{k}
    \leq \sum_{n=0}^{k-1}\binom{m}{n}(r-1)^{m-n} + (p-1)\binom{m}{k},
\]
as claimed.
\end{proof}

\cref{thm:complete-config} is enough to determine the logarithmic growth rate of $\forb(m,r,F)$ asymptotically for every $(0,1)$-configuration $F$.

\begin{corollary}\label{thm:asymptotic-log}
    The asymptotic formula $\log \forb(m,r,F) \sim m \log(r-1)$ holds as $m\to \infty$ for every fixed $(0,1)$-configuration $F$ and $r \geq 3$.
\end{corollary}
\begin{proof}
    Since $F \prec p\cdot K_k$ for some $p$ and $k$, \cref{thm:complete-config} guarantees a constant $C > 0$ so that $\forb(m,r,F) \leq Cm^{k-1}(r-1)^{m}$ for every $m$ and $r$. We may assume by complementation that $F$ contains at least one 0, in which case the configuration that contains every column with no 0's avoids $F$; this implies that $\forb(m,r,F) \geq (r-1)^m$ for every $m, r \in \N$. If $r \geq 3$ is fixed, then the logarithmic growth rates of the lower and upper bounds are asymptotically equal as $m \to \infty$.
\end{proof}

The trivial bound $\forb(m,r,F) \leq r^m$ combined with the lower bound $\forb(m,r,F) \geq (r-1)^m$ shows that $\forb(m,r,F) = \Theta(r^m)$ if $m$ is fixed and $\forb(m,r,F)$ is regarded as a function of $r$.

Going back to exact results, let $K_k^s$ denote the $k\times \binom{k}{s}$ configuration of zeros and ones in which every column contains $s$ ones, called the \textit{complete uniform configuration of weight $s$}. F\"uredi and Quinn proved in \cite{furedi1984traces} that $\forb(m,K_k^s) = \sum_{i=0}^{k-1} \binom{m}{i}$. The configuration where $s$ ones never appear above $k-s$ zeros provides the lower bound; since $K_k^s \prec K_k$, Sauer's theorem provides the upper bound. The construction easily extends, yielding the following result.

\begin{proposition}\label{thm:complete-uniform}
If $s \leq k$, then $\forb(m,r,K_k^s) = \sum_{i=0}^{k-1}\binom{m}{i}(r-1)^{m-i}$. If $(r-2)^{m-k} \geq p-1$, then $\forb(m,r,p\cdot K_k^s) = \forb(m,r,K_k^s) + (p-1)\binom{m}{k}$.
\end{proposition}
\begin{proof}
Let $A_n$ be the $n$-rowed configuration that contains every column in which $s$ ones do not appear above $k-s$ zeros. The sequence $(A_n)$ satisfies the conditions of \cref{thm:01-equal}, and an identical calculation to the one in the proof of \cref{thm:complete-config} proves the first statement.

The proof of the upper bound for the second statement is identical to the one in \cref{thm:complete-config}. For the lower bound, let $A$ be the configuration that contains every column where $s$ ones never appear above $k-s$ zeros; this configuration avoids $K_k^s$. If $(r-2)^{m-k} \geq p-1$, then for each $X \in \binom{[m]}{k}$ we can append $p-1$ columns to $A$ that have $s$ ones above $k-s$ zeros in the rows of $X$ and non-binary digits elsewhere. The resulting configuration avoids $p\cdot K_k^s$ and has $\forb(m,r,p\cdot K_k^s) = \forb(m,r,K_k^s) + (p-1)\binom{m}{k}$ columns.
\end{proof}

A matrix is called \textit{$p$-simple} if each column has multiplicity at most $p$.

\begin{corollary}\label{thm:p-simple-with-p-block}
Assume that $F$ is a $k$-rowed $p$-simple matrix such that $p\cdot K_k^s \prec F$ for some $0 \leq s \leq k$. If $(r-2)^{m-k} \geq p-1$, then
\[ \forb(m,r,F) = \sum_{n=0}^{k-1} \binom{m}{n}(r-1)^{m-n} + (p-1)\binom{m}{k}. \]
If $F$ is simple and $K_k^s \prec F$, then $\forb(m,r,F) = \forb(m,r,K_k^s) = \forb(m,r,K_k)$ for all $m \in \N$ and $r \geq 2$.
\end{corollary}
\begin{proof}
Since $p\cdot K_k^s \prec F \prec p\cdot K_k$, the statement follows from \cref{thm:complete-config,thm:complete-uniform}.
\end{proof}

The result for non-simple matrices in \cref{thm:complete-uniform} is only applicable when $r > 3$. The argument can be modified to show that $\forb(m,3,p\cdot K_k^s)$ is at most an additive constant away from $\sum_{i=0}^{k-1} \binom{m}{i}2^{m-i} + (p-1)\binom{m}{k}$.

\begin{proposition}\label{thm:non-simple-complete-uniform}
Suppose $p > 1$ and $a = \lceil \log_2(p-1)\rceil$. Then
\[ \forb(m,3,p\cdot K_k^s) \geq \sum_{i=0}^{k-1} \binom{m}{i}2^{m-i} + (p-1) \left(\binom{m}{k} - \binom{k+a-1}{k}\right). \]
\end{proposition}
\begin{proof}
Let $A$ be the configuration with all columns that do not contain $s$ ones above $k-s$ zeros. For every $k$-set $X$ with elements $i_1 < i_2 < \dots < i_k$ and $i_s + (m - i_{s+1}) - k \geq \log_2(p-1)$, we may append $p-1$ columns to $A$ with entries $\mathfrak{c}_i$ given by
\[ \begin{cases}
    \mathfrak{c}_i = 1         &\text{if } i \in X \text{ and } i \leq i_s\\
    \mathfrak{c}_i \in \{0,2\} &\text{if } i \notin X \text{ and } i \leq i_s\\
    \mathfrak{c}_i = 2         &\text{if } i_s < i < i_{s+1}\\
    \mathfrak{c}_i = 0         &\text{if } i \in X \text{ and } i \geq i_{s+1}\\
    \mathfrak{c}_i \in \{1,2\} &\text{if } i \notin X \text{ and } i \geq i_{s+1}.
\end{cases} \]
For each such column $\mathfrak{c}$, there is exactly one $k$-set $S$ (namely $S = X$) so that $\mathfrak{c}\vert_S$ is $s$ ones above $k-s$ zeros. Therefore, the resulting configuration $A'$ avoids $p\cdot K_k^s$.

To determine the number of columns added to $A$, we count the number of choices of $X$ with $i_s + (m - i_{s+1}) - k < \log_2(p-1)$. The number of choices with $i_s + (m - i_{s+1}) - k = b$ is $\binom{k-1+b}{k-1}$, so the number of choices of $X$ not covered in our strategy is
\[ \sum_{b=0}^{a-1} \binom{k-1+b}{k-1} = \binom{k+a-1}{k}. \]
In total, then $A'$ contains $(p-1)\big(\binom{m}{k} - \binom{k+a-1}{k}\big)$ more columns than $A$.
\end{proof}

\begin{corollary}\label{thm:complete-uniform-p=2}
$\forb(m,3,2\cdot K_k^s) = \sum_{i=0}^{k-1} \binom{m}{i}(r-1)^{m-i} + \binom{m}{k}$.
\end{corollary}
\begin{proof}
Applying \cref{thm:non-simple-complete-uniform} with $p=2$ gives the lower bound, and the upper bound follows from \cref{thm:complete-config} together with $2\cdot K_k^s \prec 2\cdot K_k$.
\end{proof}

\section{Identity matrices}\label{sec:identity-matrices}

Noting that $I_k = K_k^1$ yields the following corollary of \cref{thm:complete-uniform}.

\begin{corollary}\label{thm:identity-r>3}
If $r > 3$, then $\forb(m,r,p\cdot I_k) = \sum_{i=0}^{k-1}\binom{m}{i}(r-1)^{m-i} + (p-1)\binom{m}{k}$ for all $m$ such that $(r-2)^{m-k} \geq p-1$.
\end{corollary}

The main result of this section is a stability theorem for $I_2$. It would be interesting to see similar stability theorems for other complete uniform configurations.

With each configuration $A \in \Avoid(m,r,I_2)$ we can associate a tournament on $m$ vertices. Direct an edge from $i$ to $j$ if there is no column in which 0 appears in row $i$ and 1 appears in row $j$. If both $ij$ and $ji$ are possible edges, choose just one. Since $A$ avoids $I_2$, there must be an edge between each pair of vertices, so this construction gives a tournament $T_A$ on $m$ vertices.

\begin{proposition}\label{thm:stability-I2}
Let $r \geq 2$ and $A \in \Avoid(m,r,I_2)$ such that $T_A$ is not transitive. Then $\lvert A \rvert \leq m(r-1)^{m-1} + (r-1)^m - 2(r-1)^{m-3}$.
\end{proposition}
\begin{proof}
We first prove the case $r=2$: If $A \in \Avoid(k,2,I_2)$ such that $T_A$ is not transitive, then $\lvert A \rvert \leq m-1$. Since $T_A$ is not transitive, it contains a 3-cycle $ijk$. The only possible columns in $A\vert_{\{i,j,k\}}$ are $\sbb 0 \\ 0 \\ 0 \seb$ and $\sbb 1 \\ 1 \\ 1\seb$. If we delete rows $i$ and $j$, then the resulting configuration $A'$ is simple and avoids $I_2$, so $\lvert A \rvert = \lvert A' \rvert \leq \forb(m-2,I_2) = m-1$.

We now proceed with the general case. Suppose that $A \in \Avoid(m,r,I_2)$ with $T_A$ not transitive. As before, there is a 3-cycle $ijk$ in $T_A$. Applying the argument used in the proof of \cref{thm:upper-01-bound} and splitting the sum over sets that do or do not contain $\{i,j,k\}$ gives the bound
\begin{align*}
    \forb(m,r,I_2)
    &\leq \sum_{\substack{X \subseteq [m] \\ \mathclap{\{i,j,k\} \not\subseteq X}}} (r-2)^{m-\lvert X\rvert}(\lvert X \rvert+1)\,
        + \mspace{-13mu}\sum_{\substack{X \subseteq [m] \\ \mathclap{\{i,j,k\} \subseteq X}}} (r-2)^{m-\lvert X\rvert}(\lvert X \rvert-1)\\
    &= \sum_{X \subseteq [m]} (r-2)^{m-\lvert X\rvert}(\lvert X \rvert+1)\,
        -\, 2\sum_{\substack{X \subseteq [m] \\ \mathclap{\{i,j,k\} \subseteq X}}}  (r-2)^{m-\lvert X\rvert}.
\end{align*}
The left sum simplifies to
\[
    \sum_{k=0}^m \binom{m}{k}(r-2)^{m-k}(k+1) = m(r-1)^{m-1} + (r-1)^m,
\]
and the right sum is
\[
    \sum_{k=3}^m \binom{m-3}{k-3} (r-2)^{m-k}
    = \sum_{k=0}^{m-3} \binom{m-3}{k} (r-2)^{m-3-k}
    = (r-1)^{m-3}.
\]
Combining the two evaluations completes the proof.
\end{proof}

\begin{theorem}\label{thm:I2-unique}
For each integer $r \geq 2$, there is a unique extremal $r$-configuration with $m$ rows that avoids $I_2$.
\end{theorem}
\begin{proof}
By \cref{thm:stability-I2}, if $A$ is extremal, then $T_A$ is transitive. Therefore there is an ordering $i_1,\dots,i_m$ of $[m]$ so that $i_si_t$ is an edge of $T$ if and only if $s < t$. After permuting the rows of $A$ according to this order, no 0 appears above a 1. There are $m(r-1)^{m-1}$ such columns that contain a 0 and $(r-1)^m$ columns with no $0$. Since $A$ is extremal, it contains all these columns. Up to row and column permutation, therefore, $A$ is unique.
\end{proof}

Thus, there is a gap between the unique extremal configuration that avoids $I_2$ and any other configuration that avoids $I_2$ but is not a subconfiguration of the extremal one.

In another direction, \cref{thm:complete-config,thm:complete-uniform} and \cref{thm:complete-uniform-p=2} show that $\forb(m,3,p\cdot I_2) = \forb(m,3,p\cdot K_2)$ when $p=1$ or $p=2$. However, equality does not hold for higher values of $p$. The following exact evaluation of $\forb(m,r,3\cdot I_2)$ shows that $\forb(m,3,p\cdot I_k) \neq \forb(m,3,p\cdot K_k)$ in general. In contrast, \cref{thm:identity-r>3} states that $\forb(m,r,p\cdot I_k) = \forb(m,r,p\cdot K_k)$ for every $p \geq 1$ when $r > 3$.

\begin{proposition}
If $m \geq 4$, then $\forb(m,3,3\cdot I_2)

= \forb(m,3,3\cdot K_2)-1$.
\end{proposition}
\begin{proof}
Let $A$ be the configuration constructed in the proof of \cref{thm:non-simple-complete-uniform} with $\forb(m,3,3\cdot K_2) - 2$ columns that avoids $3\cdot I_2$. Appending the column $\mathfrak{c}$ with $\mathfrak{c}_1 = 1$, $\mathfrak{c}_m = 0$, and $\mathfrak{c}_i = 2$ for every $1 < i < m$ creates a configuration with $\forb(m,3,3\cdot K_2) - 1$ columns that avoids $3\cdot I_2$.

We now show that any 3-configuration that avoids $3\cdot I_2$ has at most $\forb(m,3,3\cdot K_2) - 1$ columns. In each pair of rows, either $\sbb 0 \\1 \seb$ or $\sbb 1 \\ 0\seb$ appears at most twice. Permuting the corresponding columns to the right end of the configuration $A$, we create a decomposition $A = [BC]$ where $\lvert C \rvert \leq 2\binom{m}{2}$ and $B$ avoids $I_2$. If $B$ is not the unique extremal configuration that avoids $I_2$, then
\[
    \lvert A \rvert
    = \lvert B \rvert + \lvert C\rvert
    \leq \forb(m,3,K_2) - 1 + 2\binom{m}{2}
    = \forb(m,3,3\cdot K_2) - 1.
\]
Otherwise, \cref{thm:I2-unique} shows that we may permute the rows of $B$ so it contains every column where no 0 appears above a 1. Since $B$ has at least four rows, $B|_{\{i,j\}}$ contains at least four columns of the form $\left[\begin{smallmatrix} 1 \\ 0\end{smallmatrix}\right]$ for every $i,j \in [m]$ with $i < j$.

We \textit{mark} the pair $i < j$ for each time that 0 appears in row $i$ and 1 appears in row $j$ in the configuration $C$. Since $A$ avoids $3\cdot I_2$ and $B|_{\{i,j\}}$ already contains four columns of the form $\left[\begin{smallmatrix} 1 \\ 0\end{smallmatrix}\right]$, each pair has at most two marks. Each column of $C$ contributes at least one mark. If the pair $(1,m)$ has at most one mark, then there are at most $2\binom{m}{2} - 1$ columns in $C$. If $(1,m)$ has two marks, then there is a column $\mathfrak{c}$ in $C$ with $\mathfrak{c}_1 = 0$, $\mathfrak{c}_m = 1$, and $\mathfrak{c}_s \neq 2$ for some $1 < s < m$. In this case the column $\mathfrak{c}$ contributes at least two marks: one for $(1,m)$, and one for either $(1,s)$ or $(s,m)$. So in this case, too, there are at most $2\binom{m}{2}-1$ columns in $C$. In either case,
\[
    \lvert A \rvert
    = \lvert B\rvert + \lvert C\rvert
    \leq \forb(m,3,3\cdot K_2) - 1,
\]
proving the lower bound.
\end{proof}

The upper bound in this argument shows that $\forb(m,3,p\cdot K_2) < \forb(m,3,p\cdot I_2)$ for all $p \geq 3$. Indeed, by following this mark argument, one can calculate exact forbidden numbers for larger $p$. It's not too hard to show, for example, that $\forb(m,3,4\cdot I_2) = \forb(m,3,4\cdot K_2) - 2$ and $\forb(m,3,5\cdot I_2) = \forb(m,3,5\cdot K_2) - 5$. The computations, however, rapidly become rather case-heavy as $p$ increases. In general, the mark argument can be extended to show that the difference between $\forb(m,3,p\cdot I_2)$ and $\forb(m,3,p\cdot K_2)$ is superlinear in $p$; for example,
\begin{equation}
    \forb(m,3,p\cdot I_2) \leq \forb(m,3,p\cdot K_2) - \frac{1}{4} (p-1)\log_2(p-1)\big(\!\log_2(p-1)-1\big),
\end{equation}
although this is not sharp.

\section{Block matrices}\label{sec:block-matrices}
\begin{proposition}\label{thm:vertical-block}
If $(r-2)^{m-a-b} \geq p-1$ , then
\begin{multline}\label{eqn:vertical-block-matrix}
    \forb\left(m,r,{\sbb \mathbf{0}_{a\times p} \\ \mathbf{1}_{b\times p} \seb} \right) =
    \sum_{\ell=0}^{a-1}\binom{m}{\ell}(r-1)^{m-\ell}
    + \sum_{k=0}^{b-1}\binom{m}{k}(r-1)^{m-k}\\
    -\sum_{\ell=0}^{a-1}\sum_{k=0}^{b-1}\binom{m}{\ell}\binom{m-\ell}{k}(r-2)^{m-\ell-k}
    + (p-1)\binom{m}{a}\binom{m-a}{b}.
\end{multline}
\end{proposition}
\begin{proof}
Any maximal matrix that avoids $F \coloneqq \sbb \mathbf{0}_{a\times p} \\ \mathbf{1}_{b\times p} \seb$ contains all columns that have fewer than $a$ zeros or fewer than $b$ ones. This accounts for the first three terms of \eqref{eqn:vertical-block-matrix}. Thus we need only bound the number of columns that contain at least $a$ zeros and at least $b$ ones. There are $(r-2)^{m-a-b}$ columns that contain exactly $a$ zeros and $b$ ones for a fixed $a$-set $X$ and $b$-set $Y$ of rows. If $(r-2)^{m-a-b} \geq p-1$, then for each disjoint $X, Y \subseteq [m]$ with $\lvert X \rvert = a$ and $\lvert Y \rvert = b$, we may take $p-1$ columns with 0's in the rows in $X$ and 1's in the rows of $Y$ and entries in $\{2,\dots,r-1\}$ elsewhere. This is $(p-1)\binom{m}{a}\binom{m-a}{b}$ columns, which provides the lower bound.

For the upper bound, we again use a mark argument. Consider the set of ordered pairs $(X,Y)$ where $X, Y \subseteq [m]$ are disjoint, $\lvert X \rvert = a$, and $\lvert Y \rvert = b$. Given a matrix $A$, we place a mark on the pair $(X,Y)$ for every column $\mathfrak{c} \in A$ such that $\mathfrak{c}\vert_X$ contains only zeros and $\mathfrak{c}\vert_Y$ contains only ones. There can be at most $(p-1)\binom{m}{a}\binom{m-a}{b}$ marks in total if the matrix $A$ avoids $F$. Every column that contains at least $a$ zeros and $b$ ones contributes at least one mark, so there are at most $(p-1)\binom{m}{a}\binom{m-a}{b}$ such columns, which gives the upper bound.
\end{proof}

\begin{corollary}\label{thm:0-1vector}
If $(r-2)^{m-2} \geq p-1$, then
\[
    \forb(m,r, p \cdot \sbb 0  \\ 1 \seb) = 2(r-1)^m - (r-2)^m + (p-1)m(m-1).
\]
\end{corollary}

\section{Forbidden configurations with 2 rows}\label{sec:two-rows}

We define the general 2-rowed $(0,1)$--forbidden configuration
\begin{equation}
    F(a,b,c,d) =
    \bigg[
    \underbrace{
        \begin{matrix} 0 & \cdots & 0 \\ 0 & \cdots & 0 \end{matrix}
        }_a
    \underbrace{
        \begin{matrix} 1 & \cdots & 1 \\ 0 & \cdots & 0 \end{matrix}
        }_b
    \underbrace{
        \begin{matrix} 0 & \cdots & 0 \\ 1 & \cdots & 1 \end{matrix}
        }_c
    \underbrace{
        \begin{matrix} 1 & \cdots & 1 \\ 1 & \cdots & 1 \end{matrix}
        }_d
    \bigg].
\end{equation}

Our main tools will be two reduction lemmas.

\begin{lemma}[Reduction Lemma for $r > 3$]\label{thm:reduction-r>3}
Suppose $b,c \geq 1$ and set $b' = \min\{b,c\}$. If $(r-2)^{m-2} \geq 2(\max\{b,c\} - 1)$, then
\[ \forb\!\big(m,r,F(a,b,c,d)\big) = \forb\!\big(m,r,F(a,b',b',d)\big). \]
\end{lemma}
\begin{proof}
If $b=c$ the statement is trivial, so suppose without loss of generality that $b < c$. We set $F\coloneqq F(a,b,c,d)$ and $F' = F(a,b,b,d)$. It follows from $F' \prec F$ that $\forb(m,r,F') \leq \forb(m,r,F)$. To prove the reverse inequality, we want to show that $\lvert A\rvert \leq \forb(m,r,F')$ for every $A \in \Avoid(m,r,F)$. This is true if $A$ avoids $F'$, so suppose instead that $F' \prec A$. By permuting the rows of $A$, we may assume that some instance of $F'$ appears in its first two rows. We write $A$ in the block form
\begin{equation}
    A = \begin{bmatrix}
    0 & 0 & 1 & \cdots & r-1\\
    0 & 1 & 0 & \cdots & r-1 \\
    A_{0,0} & A_{0,1} & A_{1,0} & \cdots & A_{r-1,r-1}
    \end{bmatrix}.
\end{equation}

Because $F'$ appears in the first two rows, we know that $\lvert A_{0,0} \rvert \geq a$, that $\lvert A_{0,1}\rvert, \lvert A_{1,0}\rvert \geq b$, and that $\lvert A_{1,1}\rvert \geq d$. If either of $A_{0,1}$ or $A_{1,0}$ contains at least $c$ columns, then $A$ contains $F$ in the first two rows. But $A$ avoids $F$, so $\lvert A_{1,0}\rvert, \lvert A_{0,1}\rvert < c$. We assumed that $(r-2)^{m-2} \geq 2 (c - 1)$, so it is possible to delete the columns with $\sbb 0 \\ 1\seb$ or $\sbb 1 \\ 0 \seb$ in the first two rows and append $\lvert A_{0,1}\rvert + \lvert A_{1,0}\rvert$ distinct columns $\mathfrak{c}$ to $A$ with $\mathfrak{c}_1 = 0$, $\mathfrak{c}_2 = 1$, and $\mathfrak{c}_i \notin\{0,1\}$ for $i > 2$. The resulting configuration does not contain $I_2$ in its first two rows, so it does not contain $F'$ in the first two rows, either. Moreover, this operation does not create a new instance of $F'$ in $A$.

Iterating this process for every appearance of $F'$ in $A$ produces a matrix with the same number of columns as $A$ that avoids $F'$. Thus $\lvert A\rvert \leq \forb(m,r,F')$, as desired.
\end{proof}

\begin{theorem}[Forbidden numbers for $2$-rowed $(0,1)$-matrices with $r > 3$] Let $F = F(a,b,c,d)$ and $\alpha = \max\{a,d, \min\{b,c\}\}$, and suppose $(r-2)^{m-2} \geq 2 \max\{a,b,c,d\}$. If $\alpha > 0$, then
\begin{equation}\label{eqn:2-rowed-r>3}
    \forb\!\big(m,r,F(a,b,c,d)\big) = m(r-1)^{m-1} + (r-1)^m + (\alpha - 1)\binom{m}{2}.
\end{equation}
Otherwise, $F = p\cdot \sbb 0 \\ 1 \seb$ and
\begin{equation}
\forb(m,r,p \cdot \sbb 0 \\ 1 \seb) = 2(r-1)^m - (r-2)^m + (p-1)m(m-1).
\end{equation}
\end{theorem}
\begin{proof}
The case $F = p \cdot \sbb 0 \\ 1 \seb$ is given by \cref{thm:0-1vector}. We prove the statement for $\alpha > 0$ in cases.

\textit{Case 1:} $\alpha = a$ and $b,c \geq 1$. By \cref{thm:reduction-r>3}, we may assume that $b=c$. Then $\mathbf{0}_{2\times a} \prec F$ and $F$ is $a$-simple, so the statement follows from \cref{thm:p-simple-with-p-block}. Taking the $(0,1)$-complement of $F$ handles the case $\alpha = d$ with $b,c\geq 1$.

\textit{Case 2:} $\alpha = \min\{b,c\}$. This implies $b,c\geq 1$, so by \cref{thm:reduction-r>3}, we may assume $b=c$. Then $c \cdot I_2 \prec F \prec c\cdot K_2$, so the upper bound follows from \cref{thm:complete-config} and the lower bound from \cref{thm:identity-r>3} with $k=2$.

\textit{Case 3:} $b=0$ or $c=0$. By possibly taking the complement, we may assume that $b=0$. Since the arguments are symmetric, suppose $a \geq d$, which implies that $\alpha = a$. Then $F \prec F(a,1,\max\{1,c\},d)$, so by \cref{thm:reduction-r>3},
\[  \forb(m,r,a\cdot \mathbf{0}_2)
    \leq \forb(m,r,F)
    \leq \forb(m,r,F(a,1,1,d)). \]
The lower and upper bounds are equal by \cref{thm:p-simple-with-p-block} and Case 1.
\end{proof}

Proving a reduction lemma for $r=3$ requires a different approach.

\begin{lemma}[Reduction Lemma for $r=3$]\label{thm:reduction-r=3}
Let $b' = \min\{b,c\}$. If $2^{m-2} \geq (\max\{a,b,c,d\}-1)m^2$ and $b' \geq 1$, then
\[ \forb\!\big(m,3,F(a,b,c,d)\big) = \forb\!\big(m,3,F(a,b',b',d)\big). \]
\end{lemma}
\begin{proof}
Let $p = \max\{a,b,c,d\}$, so that $F\coloneqq F(a,b,c,d)$ is $p$-simple, and set $F' = F(a,b',b',d)$. As above, $\forb(m,r,F') \leq \forb(m,r,F)$ follows from the observation that $F' \prec F$.

Now let $A \in \Avoid(m,3,F)$. We want to show that $\lvert A \rvert \leq \forb(m,r,F')$. If $A$ does not contain $F'$, this is clear, so we assume that $F' \prec A$. We write $A$ in block form as
\begin{equation}
    A = \left[
\begin{matrix}
        0 & 1 \\
        1 & 0 \\
        A_{0,1} & A_{1,0\,}
    \end{matrix}\right\vert \left.
    \begin{matrix}
        0 & 1 & 0 & 1 & 2 & 2 & 2 \\
        0 & 1 & 2 & 2 & 0 & 1 & 2 \\
        B & C & D & E & F & G & H
    \end{matrix}\right].
\end{equation}
By possibly taking the complement of $F$, we may assume that $b \leq c$. Moreover, since the statement is trivial if $b = c$, we assume that strict inequality holds. Since $F' \prec A$ but $F \nprec A$, we have that $b \leq \lvert A_{0,1} \rvert, \lvert A_{1,0} \rvert < c$. If there is a column in $B$ that is not in $D$, then we may delete the column $\sbb 0 \\ 0 \\ v \seb$ and insert the column $\sbb 0 \\ 2 \\ v \seb$ without introducing $F$ as a configuration. By replacing binary digits in the first two rows with 2's in this manner, we may assume that\vspace{-2em}
\[  \begin{minipage}{0.3\textwidth}
        \begin{align*}
            B \subseteq D \subseteq H \\
            B \subseteq F \subseteq H
        \end{align*}
    \end{minipage}
    \raisebox{-0.5em}{and}
    \begin{minipage}{0.3\textwidth}
        \begin{align*}
            &C \subseteq E \subseteq H \\
            &C \subseteq G \subseteq H.
        \end{align*}
    \end{minipage} \]

The matrices $\sbb 0 & 1 & 2 \\ D & E & H \seb$ and $\sbb 0 & 1 & 2 \\ F & G & H \seb$ both avoid $F$, so $\lvert DEH \rvert + \lvert FGH \rvert \leq 2\forb(m-1,3,F)$. Also, $B \cup C \subseteq H$. From inclusion-exclusion, $\lvert B \rvert + \lvert C \rvert - \lvert H \rvert \leq \lvert B \cap C\rvert$. Because $A$ avoids $p\cdot K_2$, we know that $B \cap C$ avoids $p\cdot K_1$, so $\lvert B \cap C \rvert \leq 2^{m-2} + (p-1)(m-2)$. Therefore
\[ \lvert A \rvert \leq
    2(c-1) + 2\forb(m-1,3,F) + 2^{m-2} + (p-1)(m-2). \]
If $2^{m-2} \geq (p-1)m^2$, then \cref{thm:complete-config} implies
\begin{align*}
    \lvert A \rvert
    &\leq 2(p-1) + 2 \forb(m-1,3,p\cdot K_2) + 2^{m-2} + (p-1)(m-2)\\
    &= (m-1)2^{m-1} + 2^m + 2^{m-2} + (p-1)m(m-1) + (p-1)m\\
    &\leq m2^{m-1} + 2^m
    = \forb(m,3,I_2).
\end{align*}
Since $I_2 \prec F'$, this shows that $\lvert A \rvert \leq \forb(m,3,F')$, completing the proof.
\end{proof}

\begin{theorem}
Suppose $\max\{a,d\} \geq \min\{b,c\}$. If $2^{m-2}\geq (\max\{a,b,c,d\}-1)m^2$, then
\begin{equation}
\forb\!\big(m,3,F(a,b,c,d)\big) = (r-1)^m + m(r-1)^{m-1} + (\max\{a,d\}-1)\binom{m}{2}.
\end{equation}
\end{theorem}
\begin{proof}
Since all arguments are symmetric, we assume that $a\leq d$ and $b \leq c$. If $b \geq 1$, then
\[ d\cdot \mathbf{1}_2 \prec F(a,b,b,d) \prec d\cdot K_2. \]
The forbidden numbers of both bounding configurations are equal by \cref{thm:p-simple-with-p-block}, and applying \cref{thm:reduction-r=3} shows that $F(a,b,b,d)$ and $F(a,b,c,d)$ have the same forbidden number. If $b = 0$ then $F(a,0,c,d) \prec F(a,1,\max\{1,c\},d)$. We have $d \cdot \mathbf{1}_2 \prec F(a,0,c,d)$, and by \cref{thm:reduction-r=3},
\[ \forb\!\big(m,3,F(a,1,\max\{1,c\},d)\big)
    = \forb\!\big(m,3,F(a,1,1,d)\big)
    \leq \forb(m,3,d \cdot K_2). \]
Again the upper and lower bounds are equal by \cref{thm:p-simple-with-p-block}.
\end{proof}

The remaining question is to evaluate $\forb\!\big(m,3,F(a,b,c,d)\big)$ when $\min\{b,c\} > \max\{a,d\}$. By the Reduction Lemma, we need only consider the case $b=c$. The smallest 2-rowed $(0,1)$-matrix whose forbidden number is not known when $r=3$ is
\[  \begin{bmatrix}
    0 & 1 & 1 & 0 & 0 \\
    0 & 0 & 0 & 1 & 1
    \end{bmatrix}. \]

\begin{section}{Forbidden configurations with 3 rows}\label{sec:three-rows}

\cref{thm:01-equal} provides a handful of results on 3-rowed forbidden matrices for free.

\begin{corollary}\label{thm:3-row}
The following forbidden numbers are exact for all $r\geq 2$ when $m\geq 3$.
\[
\begin{array}{c | c }
    F & \forb(m,r,F)\\\hline
    \rule[-1em]{0pt}{2.5em}\sbb 0 \\ 1 \\ 1 \seb \text{ or } \sbb 1 & 1 \\ 0 & 1 \\ 0 & 0 \seb  & m(r-1)^{m-1} + 2(r-1)^m - (r-2)^m - m(r-2)^{m-1}\\\hline
    \rule{0pt}{1.5em}\sbb 1 & 0 \\ 0 & 1 \\ 0 & 0 \seb \text{ or } \sbb 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \seb  & 2m(r-1)^{m-1} + (r-2)^m.
\end{array}
\]
\end{corollary}
\begin{proof}
Theorem 3.2 of \cite{small-forbidden} proves that the configuration $A_m = [\mathbf{0}_m I_m \mathbf{1}_m]$ is extremal for the second matrix in the first row of the table when $r=2$, and it is not too hard to see that $A_m$ is extremal for the first matrix, as well. The sequence $(A_m)$ satisfies the conditions of \cref{thm:01-equal}, and $\lvert A_m \rvert= m+1$ if $m\in \{0,1\}$ and $\lvert A_m\rvert = m+2$ otherwise, so for either matrix $F$, we have
\[
    \forb(m,r,F) = \sum_{k=0}^m \binom{m}{k}(r-2)^{m-k}\forb(k,F);
\]
simplifying this sum yields the expression in the first row of the table.

Let $U_m$ denote the $m\times m$ upper-triangular matrix with 1's on and above the diagonal and 0's elsewhere. Theorem 3.3 of \cite{small-forbidden} proves that $A_m = U_m \cup I_m^c \cup \mathbf{0}_m$ is an extremal configuration (when $r=2$) for both matrices in the second row of the table. Both $U_m$ and $I_m^c$ have a column with exactly one 0 and are otherwise disjoint, so $\lvert A_m\rvert = 2m$ for $m\geq 1$, and $\lvert A_0 \rvert = 1$ by convention. As before, $(A_m)$ satisfies the conditions of \cref{thm:01-equal}, so for either forbidden matrix $F$,
\begin{align*}
    \forb(m,r,F)
    &= \sum_{k=0}^m \binom{m}{k}(r-2)^{m-k}\forb(k,F)\\
    &= \sum_{k=0}^m \binom{m}{k}(r-2)^{m-k}2k + (r-2)^m\\
    &= 2m(r-1)^{m-1} + (r-2)^m,
\end{align*}
as claimed.
\end{proof}

The matrices $\sbb 1 & 0 & 1 \\ 0 & 1  & 1\\ 0 & 0  & 0\seb$ and $\sbb 1 & 0 & 0 \\ 0 & 1  & 1\\ 0 & 0  & 1\seb$ are sandwiched between the two matrices in the second row of \cref{thm:3-row}, so they have the same forbidden number. Our results, together with $(0,1)$-complementation, evaluate the exact forbidden number for all $3\times 2$ and $3\times 3$ simple matrices for $r\geq 3$ except $F = \sbb 1 & 0 \\ 0 & 1 \\ 0 & 1 \seb$. We can, however, bound $\forb(m,r,F)$ using our previous results. Theorem 3.3 in \cite{anstee-preprint} states that $\forb(m,F) \leq \frac{3}{2}m + 1$; applications of our \cref{thm:upper-01-bound} and \cref{thm:complete-uniform} show that
\[ m(r-1)^{m-1} + (r-1)^m \,\leq\, \forb(m,r,F) \,\leq\, \frac{3}{2}m(r-1)^{m-1} + (r-1)^m. \]
\end{section}

\bibliography{bibliography}
\bibliographystyle{amsplain}

\end{document}


TITLE: Definition of $\sigma - $finite
QUESTION [1 upvotes]: I have that a measure space is $\sigma - $finite if $\Omega = \cup_i^\infty E_i$ where the $E_i$ are measurable and $\mu(E_i) < \infty$.
Now, I am reading a proof, and it says that suppose a measure $\mu$ is $\sigma- $finite, then there exists $E_1 \subset E_2 \subset ...$ such that $\mu(E_i) < \infty $ and $\Omega = \cup_i^\infty E_i$. Could someone explain how this is equivalent to my definition, why are the $E_i$s all nested here?

REPLY [3 votes]: There are basically three useful variants of the "$\sigma$-finite decomposition":

$E_i$ have no relation to each other
$E_i$ are increasing.
$E_i$ are disjoint.

It is clear that 2 implies 1 and 3 implies 1. 1 implies 2 because you can write $\Omega=\bigcup_{k=1}^\infty F_k$ where $F_k=\bigcup_{i=1}^k E_i$. 1 implies 3 because you can write $\Omega=\bigcup_{k=1}^\infty G_k$ where $G_k=E_k \setminus \bigcup_{i=1}^{k-1} E_i$.


TITLE: Determining the degree of a root of unity over a cyclotomic expansion
QUESTION [0 upvotes]: For $\xi_{n} = e^{2\pi i/n}$ , determine the degree of $\xi_{7}$ over the field $\Bbb{Q}(\xi_{3})$.

How would I approach this problem? I'm having trouble starting this problem and can't find any resources that could help me. Any help will be great, thanks.

REPLY [2 votes]: Extended hints:

You probably know that $[\Bbb{Q}(\xi_7):\Bbb{Q}]=6$ and $[\Bbb{Q}(\xi_3):\Bbb{Q}]=2$, so you can deduce (how?) that the desired degree is either $3$ or $6$. The former case can happen only, if $\xi_3\in\Bbb{Q}(\zeta_7)$.
The Galois group $G=Gal(\Bbb{Q}(\xi_7):\Bbb{Q})\simeq\Bbb{Z}_7^*$ is cyclic of order six. Therefore, by Galois correspondence, it has a unique subfield of degree two.
By this answer (or many others) we see that $\sqrt{-7}\in \Bbb{Q}(\xi_7)$, so the unique quadratic subfield of $\Bbb{Q}(\xi_7)$ is $\Bbb{Q}(\sqrt{-7})$.
So if you can show that $\xi_3\notin \Bbb{Q}(\sqrt{-7})$, then it follows that $\xi_3\notin \Bbb{Q}(\xi_7)$, and you are done.


TITLE: Draw balls in the urn Probabilities
QUESTION [2 upvotes]: An urn contains $7$ balls, $4$ of which are black and the rest are white.

Starting with all $7$ balls in the urn, balls are drawn randomly with replacement.
Find the probability that among the first $5$ balls which are drawn:
a. Exactly $2$ of them are white.
b. At least $3$ of them are black.

For 1 a) I used Binomial Distribution:
$$\binom52\cdot\left(\frac37\right)^2\cdot\left(\frac47\right)^3$$
For 1 b) I used again Binomial distribution but because it is at least $3$ of them are black I did:
$$P(X=3)+P(X=4)=\binom53\cdot\left(\frac47\right)^3\cdot\left(\frac37\right)^2+\binom54\cdot\left(\frac47\right)^4\cdot\left(\frac37\right)^1=0.5711$$
Am I doing it right?

2) Starting with all $7$ balls in the urn, balls are drawn randomly without replacement until all $3$ white balls are found. What is the probability that the third white ball is found on the
a. fourth attempt? b. seventh attempt?
For $2.a$  I did:
The combinations can be:
$wwbw$
$P =\dfrac37\cdot\dfrac26\cdot\dfrac45\times\dfrac14 =\dfrac1{35}$
$wbww$
$P =\dfrac37\cdot\dfrac46\cdot\dfrac25\times\dfrac14 = \dfrac1{35}$
$bwww$
$P = \dfrac47\cdot\dfrac36\cdot\dfrac25\times\dfrac14 = \dfrac1{35}$
so : $P = \dfrac3{35}$, right?
for question $2 b)$ is there a way to do this without thinking in all possible combinations, as in the question above?

REPLY [0 votes]: $1$ is ok.
So is $2a$, though you could have done less work by just multiplying one of the expressions by $\binom31$, instead of listing the $3$ combinations.
For $2(b)$, there is a beautiful way to avoid all computations !
By symmetry, P(last ball is white) = P(first ball is white) = $\dfrac37$
PS:
What I am saying is that since balls don't have preference for positions, the probability of a white ball being found in any position = $\frac37$, the same as that for the first position.
Let's check for position $2$ as an example.
P(white ball found in position $2$) =$P(BW) + P(WW) = \frac47\cdot\frac36 + \frac37\cdot\frac26 = \frac 37$


TITLE: Show that f is continuous on x if and only if x is irrational
QUESTION [4 upvotes]: Let $f : [0, 1] → R$ be given by the formula
$f(x) = \frac{1}b$ if $x = \frac{a}b$, where $a$ and $b$ have no common factor,
$f(x) = 0$ if $x$ irrational.
Show that $f$ is continuous at $x$ if and only if $x$ is irrational. (Hint: Use the
density properties of rationals and irrationals.)

My attempt: Let $\epsilon > 0$. Suppose $x$ is irrational, then $f(x) = 0$.
$|x-x| < \delta$
$|f(x) - x| = |-x| = x$
So we can choose $\delta = \epsilon$ so that $\epsilon > x$ (I'm unsure of this part).
Suppose $x$ is rational, $f(x) = \frac{1}b$. We want to show that is discontinuous. Suppose there is a $\delta$ that works for $|\frac{1}b-x| < \epsilon$. Let $\epsilon = \frac{1}2$. Let $x= \min(\delta, \frac{3}4)$
$|\frac{1}4 - \frac{3}4| = |-\frac{1}2| = \frac{1}2$
And $1/2$ is not greater than a $1/2$. So it is a contradiction.

REPLY [0 votes]: Let $x_0$ an irrational number in $[0,1]$. You have to show that $\lim_{x\to x_0}f(x)=f(x_0)=0$. This is obvious for irrational $x$s, so all you have to prove is
$$\lim_{\substack{x\to x_0\\x\in\mathbf Q}}f(x)=0.$$
In terms of $\varepsilon$ and $\delta$, this means that, for any  $\varepsilon>0$, there exists $\delta>0$  such that
$$\biggl|\frac ab -x_0\biggr|<\delta \implies 0<\frac1b <\varepsilon,\enspace\text{i.e. }\; b>\frac1\varepsilon. $$
Indeed, there is only a finite number of positive integers $\le\dfrac1\varepsilon$. Therefore, by the  Archimedes property, the interval $[0,1]$ contains only a finite number of rational numbers $\dfrac ab$ in irreducible form with denominator  $\le\dfrac1\varepsilon$.
Choose  $\delta>0$  small  enough so the interval $(x_0-\delta, x_0+\delta)$ contains none of these fractions. Then all rational numbers $\dfrac ab$ in this interval have denominator $ b>\dfrac1\varepsilon$, hence
$$f\Bigl(\frac ab\Bigr)=\frac1b<\varepsilon.$$
The other way (continuous at $x$ implies $x$ irrational) is obvious  by contrapositive and density of the irrational numbers.


TITLE: Torque on rolling cylinder
QUESTION [2 upvotes]: Consider a rod with two equal forces acting parallel to the direction of velocity of a rolling rod, one at each end. When analysing problems involving torque, the choice of axis should not matter. However, when we consider the axis as one end of the rod, there seems to be an unbalanced torque at the other end which will cause angular acceleration. However, in reality there is no such acceleration. What causes this discrepancy?
Note: consider 2nd example in image with F1 = F2 and cylinder rolling along long end

REPLY [0 votes]: When summing torque, the choice of axis only does not matter when the net force is zero. So only in statics this is true.
Otherwise you transform torque from one place to another with $$ \boldsymbol{\tau}_A = \boldsymbol{\tau}_B + \boldsymbol{r}_{B/A} \times \boldsymbol{F}$$
Specifically in dynamics it is convenient to sum torques about the center of mass, because this decouples the equations of motion.
The center of mass has the property of decoupling momentum in translational and rotational parts
$$ \begin{aligned}
\boldsymbol{p} & = m \boldsymbol{v}_C \\
\boldsymbol{L}_C & = {\rm I}_C \boldsymbol{\omega} \\
\end{aligned} $$
and by application of Newton's 2nd law the equations of motion are also decoupled
$$ \begin{aligned}
\boldsymbol{F} & = \tfrac{\rm d}{{\rm d}t} \boldsymbol{p} = m \boldsymbol{a}_C \\
\boldsymbol{\tau}_C & = \tfrac{\rm d}{{\rm d}t} \boldsymbol{L}_C = {\rm I}_C \boldsymbol{\alpha} + \boldsymbol{\omega} \times {\rm I}_C \boldsymbol{\omega} \end{aligned} $$
A typical example of this point is when hanging a rod from the ceiling using two equal strings at its ends, and you cut one of the strings. You will find the tension on the other string only if you realize that the sum of forces is not zero  and the torque evaluated should consider that.


TITLE: How to test convergence of piecewise-defined series?
QUESTION [0 upvotes]: Examine whether the series defined as:
$$\sum a_n = \begin{cases}
 \hphantom{-}\dfrac{1}{n}, & \text{for $n$ odd} \\[8pt]
 -\dfrac{1}{5^n}, & \text{for $n$ even }
\end{cases}$$
converges.
It is some kind of alternating series and the limit test seems to give convergence, as both branches $\lim\limits_{x \to \infty} \rightarrow$ $0$ and $a_n > a_{n+1}$ , i.e. decreacing. Is all the above paragraph right?

REPLY [1 votes]: Note that when an alternating series converges conditionally, it is because the series consisting only of the positive terms AND the series consisting of the negative terms both diverge. If the series of positive terms went to $+\infty$ while the series of negative terms converged to a fixed negative number $L < 0$, then the result goes to $+\infty$. An analogous reasoning shows what happens when the series of positive terms converge and the series of negative terms goes to $-\infty$.
In symbols, if $\sum_{n=1}^{\infty} a_n$ satisfies $a_{2n} > 0$ and $a_{2n+1} < 0$, then
$$
a_{2n} \to +\infty, \quad a_{2n+1} \to L \in \mathbb R \quad \Longrightarrow \quad \sum_{n=1}^N a_n \underset{N \to \infty}{\longrightarrow} +\infty.
$$
This can be proven formally since
$$
\sum_{n=1}^{2N} a_n , \sum_{n=1}^{2N+1} a_n\ge \sum_{n=1}^N a_{2n} + \sum_{n=1}^{\infty} a_{2n+1} = \left( \sum_{n=1}^N a_{2n} \right) - L \underset{N \to \infty}{\longrightarrow} +\infty.
$$
In your case, since the series $\sum_{n=1}^{\infty} \frac 1{2n-1}$ diverges and $\sum_{n=1}^{\infty} \frac{-1}{5^{2n}}$ converges, we can use the above reasoning. It is interesting to not simply look at the example but think a bit more thoroughly and learn something from the example, which is the point I tried to make above.
(I assumed the series converges conditionally ; when it converges unconditionally, both the series of positive terms and negative terms are convergent, so this whole business is not necessary.)
Hope that helps,


TITLE: The set of all interior points. Set equality
QUESTION [0 upvotes]: $(\overline{E})^o=E^o$. Is this equality true?
I proved that inclusion $E^o\subset (\overline{E})^0$ is true. But how to prove that inclusion $(\overline{E})^0\subset E^o$ is true or false?
$E^o$ the set of all interior points of $E$ and $\overline{E}$ is the closure of a set $E$.

REPLY [0 votes]: It is false. Take for instance $E=\Bbb Q$ (in $\Bbb R$ with the usual topology).


TITLE: How many onto functions are there from a set with $5$ elements to a set with $3$ elements?
QUESTION [3 upvotes]: Consider functions from a set with $5$ elements to a set with $3$ elements.
(a) How many functions are there?
(b) How many are one-to-one?
(c) How many are onto?
a) Each element mapped to $3$ images.
   $3 \cdot 3 \cdot 3 \cdot 3 \cdot 3$
b) $0$
c) How do I do this?
Edit:
I tried doing this way.
EDIT:
There can be a set of cardinality {3,1,1} or {2,2,1}.
For {3,1,1}:
5C3 * 2C1 * 1C1 * 3!
For  {2,2,1}:
5C2 * 3C2 * 1C1 * 3!
And i realized my 3! is wrong. Should be * 3 only. Why is that so?

REPLY [5 votes]: You correctly found that there are $3^5$ functions from a set with five elements to a set with three elements.  However, this counts functions with fewer than three elements in the range.  We must exclude those functions.  To do so, we can use the Inclusion-Exclusion Principle.
There are $\binom{3}{1}$ ways of excluding one element in the codomain from the range and $2^5$ functions from a set with five elements to the remaining two elements in the codomain.
There are $\binom{3}{2}$ ways of excluding two elements in the codomain from the range and $1^5$ functions from a set with five elements to the remaining element in the codomain.
By the Inclusion-Exclusion Principle, the number of surjective (onto) functions from a set with five elements to a set with three elements is

 $$3^5 - \binom{3}{1}2^5 + \binom{3}{2}1^5$$


text:
\section{ShieldNN}
\label{sec:shieldnn}

\begin{wrapfigure}[23]{r}{0.35\textwidth}
    \centering
    \vspace{-20mm}
    \begin{subfigure}[t]{0.33\textwidth}
		\hspace*{-17pt}
		\includegraphics[width=1.1\linewidth]{safe_controls_lr=2_rBar=4_sigma=0p48.pdf}

		\vspace{-1.25mm}
	\caption{Safe/unsafe steering controls. $\cup_\xi R_{4,0.48}((r_\text{min}(\xi),\xi,\cdot))$

	is shown in light green; $\mathfrak{l}$ and $\mathfrak{u}$ in dark green.}
	\label{fig:practical_safe_controls}

	\end{subfigure}
	\vspace{0.5mm}
	~\\

	\begin{subfigure}[t]{0.33\textwidth}
		\hspace*{-15pt}
		\includegraphics[width=1.1\linewidth,trim={0 0cm 0 0}]{clipping_plot_2.pdf}
		\vspace{-3mm}
		\caption{
		Illustration of $\nn_{\negthinspace 0}$ (orange) and two constant-$\xi$ slices of the final ShieldNN filter, $\nn$ (black). \vspace{-2mm}
		}

		\label{fig:shieldnn_design}
	\end{subfigure}\vspace{0.5mm}
	\caption{Illustrated ShieldNN products for $\ell_f = \ell_r = 2 \;\text{m}$, $\bar{r} = 4 \;\text{m}$, $\beta_\text{max} = 0.4636$, $\sigma = 0.48$.}
\end{wrapfigure}

\textbf{ShieldNN Verifier:}
The overall ShieldNN algorithm has three inputs: the specs for a KBM robot
($\ell_f=\ell_r$, $\delta_{f,\text{max}}$ and $v_\text{max}$); the desired
safety radius ($\bar{r}$); and the barrier parameter $\sigma$. From these
inputs, the ShieldNN verifier first soundly verifies that these parameters lead
to an actual barrier function for \cref{prob:main_problem}. As per
\cref{thm:safe_control_region_grows}, it suffices to show that
$R_{h_{\bar{r},\sigma}}\negthinspace((r_\text{min}(\xi),\xi,\cdot))$ is
non-empty for each $\xi \in [-\pi,\pi]$.

If the sets $R_{h_{\bar{r},\sigma}}\negthinspace
((r_\text{min}(\xi),\xi,\cdot))$ have a complicated structure (both themselves
and relative to each other), then establishing this could in principle be quite
difficult. However, the barrier functions under consideration actually appear
to  generate quite nice regions of safe controls. In particular, it appears to
the case that the set of safe steering angles in any particular orientation
state is an \emph{interval} clipped at the maximum/minimum steering inputs.
That is each such set can be written as:
\begin{equation*}
	R_{h_{\bar{r},\sigma}}\negthinspace ((r_\text{min}(\xi),\xi,\cdot))
	=
	\big[
		\max\{ -\beta_\text{max}, \mathfrak{l}(\xi) \}, \;
		\min\{  \beta_\text{max}, \mathfrak{u}(\xi) \} \;
	\big],
\end{equation*}
where $\mathfrak{l}$ and $\mathfrak{u}$ are continuous functions of $\xi$. Even
more helpfully, the function $\mathfrak{l}$ generally appears to be
\emph{concave}, and the symmetry of the problem dictates that
$\mathfrak{u}(\xi) = -\mathfrak{l}(-\xi)$. See
\cref{fig:practical_safe_controls} for an example with parameters $\ell_f =
\ell_r = 2 \;\text{m}$, $\bar{r} = 4 \;\text{m}$, $\beta_\text{max} = 0.4636$
and $\sigma = 0.48$; $\cup_{\xi\in [-\pi,\pi]}R_{h_{\bar{r},\sigma}}
\negthinspace ((r_\text{min}(\xi),\xi,\cdot))$ is shown in light green, and
$\mathfrak{l}$ and $\mathfrak{u}$ are shown in dark green.

Of course these observations about $\mathfrak{l}$ and $\mathfrak{u}$ are
difficult to show analytically, given the nature of the equations (c.f.
\eqref{eq:zbf_full}). Nevertheless, we can exhibit a sound algorithm to verify
these claims for particular parameter values, and hence that the input
parameters correspond to a legitimate barrier function. Due to space
constraints, the details of this algorithm appear in the supplementary
material.

\textbf{ShieldNN Synthesizer:}
Given a verified barrier function, recall from \textbf{(3)} in
\cref{sec:approach} that synthesizing a ShieldNN filter requires two
components: $\nn_{\negthinspace0}$ and $\nn$. That is $\nn_{\negthinspace0}$
chooses a \emph{safe} control for each state, and $\nn$ overrides any
\emph{unsafe} controls with the output of $\nn_{\negthinspace0}$.

	\begin{minipage}[t]{\linewidth}

	\parshape 2 10pt \dimexpr\linewidth-10pt 20pt \dimexpr\linewidth-20pt\relax

	\textbf{Design of }$\nn_{\negthinspace0}$\textbf{.}
	This task is much easier than it otherwise would be, since the ShieldNN
	verifier also verifies the safe controls as lying between the continuous
	functions $\max\{-\beta_\text{max}, \mathfrak{l}\}$ and
	$\min\{\beta_\text{max},\mathfrak{u}\}$ where $\mathfrak{l}$ and is concave
	and $\mathfrak{u}(\xi) = - \mathfrak{l}(-\xi)$. In particular, then, it is
	enough to design $\nn_{\negthinspace0}$ as any neural network such that
	\begin{equation}
		\max\{-\beta_\text{max}, \mathfrak{l}\}
		\leq
		\nn_{\negthinspace0}
		\leq
		\min\{\beta_\text{max},\mathfrak{u}\}.
	\end{equation}
	This property can be achieved in several ways, including training against
	samples of $\max\{-\beta_\text{max}, \mathfrak{l}\}$ for example. However,
	we chose to synthesize $\nn_{\negthinspace0}$ directly in terms of tangent
	line segments to $\mathfrak{l}$ (and thus exploit the \emph{concavity} of
	$\mathfrak{l}$). A portion of just such a function $\nn_{\negthinspace0}$
	is illustrated by the orange line in \cref{fig:shieldnn_design}.
	\end{minipage}

	\begin{minipage}[t]{\linewidth}

	\parshape 2 10pt \dimexpr\linewidth-10pt 20pt \dimexpr\linewidth-20pt\relax

	\textbf{Design of }$\nn$\textbf{.}
	Since the value of $\nn_{\negthinspace0}$ is designed to lie inside the
	interval of safe controls, the function $\nn_{\negthinspace0}$ can itself
	be used to decide when an unsafe control is supplied. In particular, using
	this property and the symmetry $\mathfrak{u}(\xi) = -\mathfrak{l}(-\xi)$,
	we can simply choose
	\begin{equation}
		\nn : \beta \mapsto \min\{
			\max\{ \nn_{\negthinspace0}(\beta), \beta \},
			-\nn_{\negthinspace0}(-\beta)
			\}.
	\end{equation}
	Note: in this construction, the closer $\nn_{\negthinspace0}$ approximates
	its lower bound, $\max\{-\beta_\text{max},\mathfrak{l}\}$, the less
	intrusive the safety filter will be. Two constant-$\xi$ slices of such a
	$\nn$ are shown in \cref{fig:shieldnn_design}.
	\end{minipage}