Relation between $[L \cap M : K \cap M]$ and $[L : K]$, and the Gauß-Wantzel theorem

The well-known Gauß-Wantzel Theorem states that a real number $ x$ can be constructed using straightedge and compass only if the minimal polynomial of $ x$ (over the field $ \mathbf Q$ ) has degree of form $ 2^n$ , $ n \in \mathbf N$ .

Is is a corollary of a more general theorem, named “Wantzel Theorem” in French, which (under the form I know) states that :

Wantzel Theorem

The real number $ x$ can be constructed using straightedge and compass if and only if there exists a sequence of commutative fields $ L_0 \subset L_1 \subset … \subset L_n$ such that:

  1. $ L_0 = \mathbf Q$
  2. $ x \in L_n$
  3. For all $ i = 1, …, n$ , $ [L_i : L_{i-1}] = 2$

I wonder whether in the latter theorem, condition 2 could be replaced by $ L_n = \mathbf Q[x]$ .

Of course, this constraint 2′ implies constraint 2, so we have one implication.

To get the other implication, I assume I have a sequence $ L_0 \subset L_1 \subset … \subset L_n$ matching conditions 1, 2 and 3, and I set for $ i = 0, …, n$ , $ L’_i = L_i \cap \mathbf Q[x]$ . Then I need to prove that for $ i=1, …,n$ , $ [L’_i : L’_{i-1}] \le 2$ .

My question is: is the latter statement true?

In a more general way, if $ L$ is a finite extension of field $ K$ , and $ M$ is another field, what can we say about $ [L \cap M : K \cap M]$ ?

Thanks in advance!

Do class features that give a flying speed count as magical in relation to falling rules?

There are some classes, like the vengeance paladin’s capstone or the Tempest Cleric’s 17th level Stormborn feature, that grant a flying speed to a creature.

Is this considered ‘magical’ flight or is it mundane flight?

I’m thinking of this with regard to the rules on falling when a creature has their speed reduced to 0 or if knocked prone:

If a flying creature is knocked prone, has its speed reduced to 0, or is otherwise deprived of the ability to move, the creature falls, unless it has the ability to hover or it is being held aloft by magic

Relation between two different functionals: $\lVert p^{-\max}_{-\varepsilon}\rVert$ and $\kappa_{p}^{-1}(1-\varepsilon)$

Given a non-negative sequence $ p=(p_i)_{i\in\mathbb{N}}\in \ell_1$ such that $ \lVert p\rVert_1 = 1$ ,we define the two following quantities, for every $ \varepsilon \in (0,1]$ .

  1. Assuming, without loss of generality, that $ p$ is non-increasing, let $ k \geq 1$ be the smallest integer such that $ \sum_{i\geq k} \leq \varepsilon$ . Then we define $ $ \Phi(\varepsilon, p) := \left( \sum_{i=2}^{k-1} p_i^{2/3} \right)^{3/2} \tag{1} $ $ i.e., the $ 2/3$ -quasinorm $ \lVert p_{-\varepsilon}^{-\max{}} \rVert_{2/3}$ of the vector $ p^{-\max{}}_{-\varepsilon}$ obtained by removing the largest element and the $ \varepsilon$ -tail of $ p$ .
  2. Defining, for $ t>0$ , the $ K$ -functional between $ \ell_1$ and $ \ell_2$ $ $ \kappa_p(t) = \inf_{a+b=p} \lVert a\rVert_1 + t \rVert b\rVert_2 $ $ and letting $ $ \Psi(\varepsilon, p) := \kappa_p^{-1}(1-\varepsilon) \tag{2} $ $ (right inverse, IIRC)

then can we prove upper and lower bounds relating (1) and (2)? Recent works of Valiant and Valiant [1] and Blais, Canonne, and Gur [2] imply such relation in a rather roundabout way (for $ p$ ‘s nontrivially point masses, i.e., say, $ \lVert p\rVert_2 < 1/2$ ) (by showing both quantities “roughly characterize” the sample complexity of a particular hypothesis testing problem on $ p$ seen as a discrete probability distribution), but a direct proof of such a relation isn’t known (at least to me), even only a loose one.

Is there a direct proof relating (upper and lower bounds) $ \Phi(\cdot, p)$ and $ \Psi(\cdot, p)$ , of the form $ $ \forall p \text{ s.t. } \lVert p\rVert \ll 1,\forall x, \qquad x^\alpha \Phi(c x, p) \leq \Psi(c x, p) \leq x^\beta \Phi(C x, p) $ $ ?

[2] (following some previous work of Montgomery-Smith [3]) does show a relation between (2) and a third quantity interpolating between $ \ell_1$ and $ \ell_2$ norms, $ $ T\in\mathbb{N} \mapsto \lVert p\rVert_{Q(T)} := \sup\{ \sum_{j=1}^T \left( \sum_{i\in A_j p_i^2 }\right)^{1/2} A_1,\dots,A_t \text{ partition of }\mathbb{N}\} \tag{3} $ $ as, for all $ t>0$ such that $ t^2\in \mathbb{N}$ , $ $ \lVert p\rVert_{Q(t^2)} \leq \kappa_p(t) \leq \lVert p\rVert_{Q(2t^2)}. $ $

[1] Gregory Valiant and Paul Valiant. An Automatic Inequality Prover and Instance Optimal Identity Testing. SIAM Journal on Computing 46:1, 429-455. 2017.

[2] Eric Blais, Clément Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory (TOCT), 11(2), 2019.

[3] Stephen J. Montgomery-Smith. The distribution of Rademacher sums. Proceedings of the American Mathematical Society, 109(2):517–522, 1990.

Passport queue length in UK in relation to arrival method

If an EU citizen arrives to the UK, would there be any difference in relation to passport queue length if different arrival methods (i.e. transportation) were used? For example, would the passport queue be typically longer at the airport than at the land border or sea port? Or does it entirely depend on the season and not on the means of transportation?

Determine relation between many keys

I have many keys of short length (6 bytes) and I know some factors that might be used to calculate them. I know for sure that the can be obtained with the given information.

Since the keys are very short and so are also the factors that may be involved in the generation, I was wondering what would be the approach of discovering how they are generated.

Multiple keys have in common the same UID and differentiated by the “block” of data they authenticate, for example (all values are in hex):

UID: 8de73004  Keys generated for this UID: 1b47cf796936 (block 15) d53c00f53a3d (block 14) 5f42136fec45 (block 13) 3b1547f2ee91 (block 12) 

I also assume there’s a private key involved in the process.

Is there a particular approach to do this? Or are there simply too many possibilities that it’s not worth it?

If well-founded induction holds, then the relation $\to$ on a reduction system terminates

I am trying to understand a proof from “Term Rewriting and All That” by Baader and Nipkow.

Well-founded induction (WFI) is the following statement:

$ \forall x \in A(\forall y \in A(x \stackrel{+}{\to}y \Rightarrow P(y))\Rightarrow P(x)) \Longrightarrow \forall x\in A (P(x))$

Here is the proof I cannot understand.

Theorem: If well-founded induction holds, then the relation $ \to$ on a reduction system terminates.

Proof: by WFI, where $ P(x):=$ “there exist no infinite chain starting from $ x$ “. The induction step is simple: If there exist no infinite chains starting from any successor of $ x$ , then there exist no infinite chains starting from $ x$ . Hence, the premise of WFI holds, and we can conclude that $ P(x)$ holds for all $ x$ i.e., $ \to$ terminates.

Why can we define $ P(x)$ to be “there exist no infinite chain starting from $ x$ “?

When does $|R_n|/|P_n| \rightarrow 0$ imply $|R_n/{\sim}| / |P_n/{\sim}| \rightarrow 0$ for an equivalence relation $\sim$?

Here is, maybe, a not very well-posed question:

Let $ P_n$ be a sequence of sets such that their sizes are non-decreasing.

Let $ R_n \subset P_n$ be a sequence of sets such their sizes are also non-decreasing.

Let $ \sim$ be an equivalence relation (the same relation) on each set $ P_n$ .

Assume that $ \frac{|R_n|}{|P_n|} \rightarrow 0$ as $ n \rightarrow \infty$ .

Question: Do we know under what hypotheses (on the $ P_n$ s, the equivalence relation $ \sim$ , $ R_n$ s, etc) does $ \frac{|R_n/\sim|}{|P_n/\sim|} \rightarrow 0$ ? If it is known, then I would love a resource.

Here is an example where the proportion of equivalence classes doesn’t go to zero even when the actual proportion of the subsets goes to zero:

Take $ R_n = \{2^i| 1 \leq i \leq n\}$ and $ P_n = \{\text{non-zero even numbers} \leq 2^n\}$ .

Define $ x \sim y$ if and only if $ x \equiv y \mod 4$ .

Then we know that $ \frac{|R_n|}{|P_n|} \rightarrow 0$ . But, $ |P_n/{\sim}| =|R_n/{\sim}| = 2$ for $ n > 1$ .

Hence, $ \frac{|R_n/\sim|}{|P_n/\sim|} \rightarrow 1$ .