context free – Formal proof of existence of equivalent parse tree for each derivation

Proposition 6.11

Full manuscript:

Definition 3.11.2: Given a context-free grammar $G = (V, Sigma, P,
> S)$
, for any $A in N$, if $pi: A stackrel{n}{implies} alpha$ is a
derivation in $G$, we construct an A-derivation tree $t_pi$ with
yield $alpha$ as follows.

  1. if $n = 0$, then $t_pi$ is the one-node tree such that $dom(t_{pi}) = { epsilon }$ and $t_{pi}(epsilon) = A$
  2. if $A stackrel{n-1}{implies} lambda B rho$ and if $t_1$ is the A-derivation tree with yield $lambda B rho$ associated with the
    derivation $A stackrel{n-1}{implies} lambda B rho$, and if $t_2$
    is the tree associated with the production $B rightarrow gamma$
    that is, if $gamma = X_1 dots X_n$,

then $dom(t_2) = { epsilon, 1, dots, k }$, $t_2(epsilon) = B$,
and $t_2(i) = X_i$ or all $i$, $1 leq i leq k$, of if $gamma = epsilon$

then $dom(t_2) = { epsilon, 1 }$, $t_2(epsilon) = B$, and $t_2(1) = epsilon$,

then $t_{pi} = t_1(u gets t_2)$, where $u$ is the address of the
leaf labeled $B$ in $t_1$.

The tree $t_{pi}$ is the A-derivation tree associated with the
derivation $A stackrel{n-1}{implies} alpha$.

enter image description here
enter image description here

finite automata – Existence of infinite unique FSAs

It is reasonably simple to show that there are an infinite number of different finite state automata that can be constructed, but has it been proven if there is an infinite number of unique finite state automata? Meaning no automata that recognize the same language.

I asked my professor and he didn’t know, and I haven’t been able to find anything about it online.

algorithms – Proving existence of an optimal substructure for the DP problem “Sherlock and Cost” from HackerRank

Problem statement from HackerRank ( source: ) :

In this challenge, you will be given an array $ B $ and must determine an array $ A $ . There is a special rule: For all $ i$, $ A(i) leq B(i) $ , . That is, $ A(i) $ can be any number you choose such that $ 1 leq A(i) leq B(i) $ . Your task is to select a series of $ A(i) $ given $ B(i) $ such that the sum of the absolute difference of consecutive pairs of $ A $ is maximized. This will be the array’s cost, and will be represented by the variable $ S $ below.
The equation can be written: $ S = sum_{i=2}^{N}{ ( A(i) – A(i-1) )} $
For example, if the array $ B = (1,2,3) $ , we know that $ 1 leq A(1) leq 1 $ , $ 1 leq A(2) leq 2 $ , and $ 1 leq A(3) leq 3 $ . Arrays meeting those guidelines are:
(1,1,1), (1,1,2), (1,1,3)
(1,2,1), (1,2,2), (1,2,3)
Our calculations for the arrays are as follows:
|1-1| + |1-1| = 0 , |1-1| + |2-1| = 1, |1-1| + |3-1| = 2
|2-1| + |1-2| = 2 ,|2-1| + |2-2| = 1 ,|2-1| + |3-2| = 2
The maximum value obtained is 2.

My attempt for proving the existence of an optimal substructure:
Denote $ SEQ $ as the set of all sequences $ A $ s.t. $ forall 1 leq i leq n $, $ 1 leq A(i) leq B(i) $. For all $ A in SEQ $ define $ S_A = sum_{i=2}^{n}{ ( A(i) – A(i-1) )} $ .

Let $ hat{A} in SEQ $ s.t. for every $ hat{A’} in SEQ $, $ S_hat{A’} leq S_hat{A} $.
Thus, there exist a sequence of optimal choices $ langle o_1,o_2,…,o_n rangle $ s.t. for all $ 1 leq i leq n $ we chose $ 1 leq alpha leq B(i) $ s.t. $ alpha in B $ and we define $ hat{A}(i) = alpha $, and this is the $ o_i $ choice.
Looking at the sequence of choices $ langle o_1,o_2,…,o_{n-1} rangle $ and looking at the sequence $ tilde A $ that derives from these choices, $ tilde A $ must be optimal. Otherwise, there exist a sequence of choices $ < o_1,…,o_l > $ s.t. $ l < n-1 $ and note that the sequence of choices $ < o_1,…,o_l, o_n > $ give $ hat{A} $. Notice that we have $ l+1 $ choices in the sequence $ < o_1,…,o_l > $ and notice that $ langle o_1,o_2,…,o_n rangle $ is an optimal sequence of choices, but $ l+1 < n $ and since every sequence of choices that yields $ hat{A} $ must have at-least $ n$ choices, this means $ n leq l+1 < n $ , a contradiction.

What do you think about this attempt? how would you prove the existence of an optimal substructure?

Thanks in advance for any help!

algorithms – Proving existence of an optimal substructure for the DP problem “Equal” from HackerRank

Let $langle o_1, o_2, o_{m+1}rangle$ be a non-empty optimal sequence of operations that distributes the chocolates evenly, i.e., such that the final distribution is $(k,k,k, dots, k)$.

Let $alpha_i$ be the number of candies given to the $i$-th person by operation $o_{m+1}$ and consider the subsequence of operations $langle o_1, o_2, dots, o_mrangle$. We need to show that $langle o_1, o_2, dots, o_mrangle$ is an optimal sequence of operations to obtain the final distribution $(k-alpha_1, k-alpha_2, dots, k-alpha_n)$.

The proof is by contradiction. Suppose that $langle o_1, o_2, dots, o_mrangle$ is not optimal, hence there is some sequence of operations $langle o’_1, o’_2, dots, o’_ell rangle$ that yields the final distribution $(k-alpha_1, k-alpha_2, dots, k-alpha_n)$ and such that $ell < m$.
Therefore, the sequence $langle o’_1, o’_2, dots, o’_ell, o’_{m+1} rangle$ yields the distribution $((k-alpha_1) + alpha_1, (k-alpha_2) + alpha_2, dots, (k-alpha_n) + alpha_n) = (k, k, dots, k)$.
The number of operations of the above sequence is $ell + 1$ and, by the optimality of $langle o_1, o_2, dots, o_{m+1}rangle$, we know that $ell+1 ge m+1$ since every sequence that yields $(k,k,dots,k)$ must consist of at least $m+1$ operations.
This results in the contradiction $m+1 le ell+1 < m+1$.

finite fields – Existence of a polynomial $Q$ of degree $geq (p-1)/4$ in $mathbb F_p[x]$ such that $QQ’$ factorizes into distinct linear factors

For all primes up to $p=53$ there exists a product $Q=prod_{j=1}^d(x-a_j)$ involving $dgeq (p-1)/4$ distinct linear factors $x-a_j$ in $mathbb F_p(x)$ such that $Q’$ has all its roots in $mathbb F_p$. Since $Q$ has only simple roots,
the product $QQ’$ has also only simple roots.

(It is obvious that a factorization into distinct linear factors of $QQ’$ implies that $Q$ has degree at most $(p+1)/2$. My computations suggest however that it seems to be hard to go substantially beyond $p/4$.)

An example for $p=53$ is given by
with derivative $$Q’=13(x^2-4^2)(x^2-13^2)(x^2-19^2)(x^2-20^2)(x^2-21^2)(x^2-22^2).$$
(I did a search over all polynomials up to $p=23$ and restricted then my attention to polynomials which are either even or odd up to $p=53$.)

Adopting a very naive viewpoint, the existence of such a polynomial of degree $geq lambda p$ for some $lambda>0$ and for almost all primes would be somewhat surprising: There are ${pchoose lambda p}$ such polynomials of degree $lambda p$
given as a product of $lambda p$ distinct linear factors
in $mathbb F_p(x)$. Adopting the very
naive viewpoint that derivatives of these polynomials behave randomly with respect to decomposition into irreducible factors,
the probability for such a polynomial $Qinmathbb F_p(x)$ (with $QQ’$ factorizing completely into distinct linear factors) to exist should be roughly given by $$left(lambda^{2lambda}(1-lambda)^{2(1-lambda)}p^lambdaright)^{-p}$$ (up to polynomial contributions) which decays exponentially fast.

Question: Can this naive argument be made rigourous or
do such polynomials of degree at least $(p-1)/4$ (or perhaps of degre at least $lambda p$ for some $lambda >0$) exist for all primes?

Motivation: The analogous question is open for degree $7$ over $mathbb Z(x)$ (existence of a polynomial $Qinmathbb Z(x)$ of degree $7$ such that $QQ’$ has $13$ distinct roots in $mathbb Z$), see proposition 27 of Proposals for polymath projects.

A stronger question (over finite fields) is to ask for
polynomials of maximal degree in $mathbb F_p(x)$ such that $Q$ and all its derivatives $Q^{(1)},Q^{(2)},ldots$ factorize into distinct linear factors.
One can either admit or forbid common roots among different derivatives. Forbidding them gives of course the trivial upper bound
$O(sqrt{p})$ on the maximal degree. I guess that admitting them does not allow substantially higher degrees.

Given an integer $d$, I guess that such polynomials of degree $geq d$ exist in $mathbb F_p(x)$ except for a finite number of small primes. (A bug in my code made me think that there are no such polynomials of degree $geq 6$ which prompted me to post a now deleted question on MO.)

It would of course be interesting to have information on the maximal degree $d_p$ for (the two versions of) this stronger question. (Interestingly, the stronger question is computationally slightly easier since the set of all such polynomials (not necessarily of maximal degree) is closed under derivation.)

pr.probability – Conditions for existence of a distribution with full support

Consider a $6times 1$ continuous random vector
etaequiv (eta_1,eta_2,…, eta_6)

satisfying the following property:
end{pmatrix}}_{equiv x_1} sim underbrace{begin{pmatrix}
end{pmatrix}}_{equiv x_2} sim underbrace{begin{pmatrix}
end{pmatrix}}_{equiv x_3} sim underbrace{begin{pmatrix}
end{pmatrix}}_{equiv x_4} sim G

where “$sim$” denotes “distributed as” and $G$ is some distribution with support $subseteq mathbb{R}^3$.

Question: I am looking for necessary and sufficient conditions on the support of $G$ such that there exists a $4times 1$ random vector $epsilon equiv (epsilon_0, epsilon_1,epsilon_2,epsilon_3)$ having an absolutely continuous distribution with full support on $mathbb{R}^4$ and such that
$$ (*) quad quad
eta_1= epsilon_1-epsilon_0\
eta_2= epsilon_2-epsilon_0\
eta_3= epsilon_3-epsilon_0\
eta_4= epsilon_1-epsilon_2\
eta_5= epsilon_1-epsilon_3\
eta_6= epsilon_2-epsilon_3\

In particular, I would like to understand the following:

A) if the distribution of $epsilon$ has full support on $mathbb{R}^4$, then $G$ CANNOT have full support on $mathbb{R}^3$. Is this correct? Why?

B) if A is correct, then there should be certain boxes in
$mathbb{R}^3$ where $G$ is zero. Can we characterise those boxes?

gn.general topology – Existence of a quasi-open (a.k.a semi-open) map into a Cantor cube

Recall that a topological space is extremally disconnected if the closure of any open set is open.

A continuous map is quasi-open if it maps open sets onto sets with nonempty interior. For some reason this class of maps shows up in the literature under different names, the most common of which is semi-open.

If $K$ is an extremally disconnected compact Hausdorff space without isolated points does the exist an infinite cardinal $alpha$ and a quasi-open map $varphi:Kto{0,1}^alpha$?

set theory – Existence of a winning strategy in the $boldsymbol{Delta}_2^0$ game

Consider the following infinite perfect information game with two players (the name I gave in the title of the post it totally made up): at each round $i in omega$, player $mathrm{I}$ picks a natural number $x_i$ and a $boldsymbol{Delta}_2^0$ subset of the Baire space $omega^omega$ denoted by $A_i$ such that $A_{i-1}subseteq A_i$ for all $i$; player $mathrm{II}$ then picks a boolean value $y_i in {0,1}$.


So at the end of the game player $mathrm{I}$ will have built an infinite sequence $x = (x_n)_{n in omega}$ and an increasing chain (wrt set inclusion) of $boldsymbol{Delta}_2^0(omega^omega)$ sets $(A_n)_{n in omega}$ whilst player $mathrm{II}$ will have built a boolean sequence $y = (y_n)_{n in omega}$ (an element of the Cantor space). Player $mathrm{II}$ wins the play if at least one of these conditions is satisfied:

  • $bigcup_{n in omega} A_n notin boldsymbol{Delta}_2^0(omega^omega)$
  • The sequence $y$ is eventually constant, i.e. $exists k forall n ge k y_n = y_k$. Moreover The sequence $y$ is eventually equal to $1$ if and only if $x in bigcup_{n in omega} A_n$. Intuitively we require player $mathrm{II}$ to “guess” whether the real played by $mathrm{I}$ will or won’t belong to the set $mathrm{I}$ is building.

Now I’m wondering whether player $mathrm{II}$ has a winning strategy in this game, or if the game is determined, and, eventually, under which hypotheses.

In a simpler game, in which player $mathrm{I}$ does not keep changing the sets $A_i$, player $mathrm{II}$ has a winning strategy
(see, for this result and a wider discussion, this paper by Raphael Carroy Playing in the first Baire class, specifically Proposition 3.10).

Any idea? Thanks