10

This is a result of joint efforts with Fedor Petrov.
First, we show that the L.H.S. of the general version does not depend on $P$ and $Q$, and then we compute that constant for some properly chosen $P$ and $Q$. The elements of $\mathcal M$ are called admissible matrices.
Part 1. We show that the L.H.S. does not depend on $P_{11}$ and $Q_{11}$; the rest is ...

8

Let $k:=\pi(n)$, so that $p_k\le n<p_{k+1}$, where $p_k$ is the $k$th prime. By the last displayed formula in this section of the Wikipedia article,
\begin{equation*}
-1+\ln(k\ln k)<\frac{p_k}k<\ln(k\ln k)
\end{equation*}
if $k\ge6$, whence
\begin{equation*}
n>-k+k\ln(k\ln k),\quad n/2<m_k:=\frac{k+1}2\,\ln((k+1)\ln(k+1)).
\end{equation*}
...

6

I believe the following works, but I might be missing something.
If $x$ has at least two 1s, then $\phi(x)$ is the sequence cut just before the last 1:
$$\phi(0011101000\cdots) = 001110 $$
If $x$ has at most one 1, then $\phi(x)$ is the sequence cut before the one, with an additional zero:
$$ \phi(000\cdots) = \varnothing,\qquad \phi(001000\cdots) = 000 $$
...

4

Edit: By request, I have added some explanations at the end. The first bullet may be helpful (it introduces a little notation). I also misread the question, and used a constant $k=3$ (instead of $k\ge 3$). This is now fixed, but $k$ must be fixed; for now the resulting bound depends on it...
Edit 2: I have added an idea on how to eliminate this issue, and (...

4

Let $\tau$ denote the permutation matrix corresponding to $(1,2,\ldots,n)$. Consider it first as an element of $\mathrm{M}_n(q^2)$.
This matrix has minimal polynomial equal to $X^n-1$, which is equal to its characteristic polynomial. It is therefore cyclic, and its centralizer is isomorphic to $\mathbb{F}_{q^2}$-algebra $\mathbb{F}_{q^2}[X]/(X^n-1)$. For ...

4

Your reasoning is correct in that the discrete Laplacian for periodic boundary conditions has a zero mode. On the space of fields satisfying $\sum_x\phi(x)=0$, its spectrum is, however, strictly positive, and it can be inverted on that space. This is all well known.

3

1: Hopes. Let me begin by taking away your hope - that is, disproving the conjectured asymptotic, $|{\mathscr{T}_{n,k}}|/2^{2^n} \to 1$.
I will say that a family $\mathcal{F}$ is $k$-rich if for each $j \in [n]$ and $w \in \{0,1\}^k$, there is $f \in \mathcal{F}$ with $f|_{[j,j+k)} = w$. Accordingly, I will say that a pair $(j,w) \in [n] \times \{0,1\}^k$ "...

3

Add to your motivating example a fifth vertex called $4$ and make it adjacent to all of $0,1,2,3$. This graph is $3$-colorable (by the $2$-coloring of your example and a third color for vertex $4$) but if you collapse $0$ with $3$ you get the complete graph on $4$ vertices, which needs four colors. And the distance from $0$ to $3$ is $2$, via vertex $4$.

3

Many properties of the vertex figures of cyclic polytopes can be obtained from Gale evenness condition.
Let $P=C(n,d)$ be a cyclic $d$-polytope, and let $v_1<\cdots<v_n$ be its vertices ordered according to the moment curve. The following follows from Gale evenness condition.
In even dimensions, the vertex figure of $P$ at every vertex is a cyclic ...

2

If I am not misunderstanding,
it could be that this $\mathbb{R}^2$ example shows that $S_5$
cannot simultaneously satisfy these relationships:
\begin{eqnarray}
S_1 \cap S_2 & \subset & S_5 \\
S_3 \cap S_4 & \subset & S_5 \\
S_2 \cap S_3 & \not\subset & S_5 \\
S_1 \cap S_4 & \not\subset & S_5 \\
\end{eqnarray}
&...

1

The sum in question can be written (using Latin letters instead of Greek) as
$$ S_n(a,b):= \sum_{k=0}^n {n \atopwithdelims \{ \} k} k! \binom{na}{k} b^k $$
where the round brackets denotes an ordinary binomial. It will be shown as $n \to \infty$
$$ (1)\quad S_n(a,b) \sim \frac{n!}{2}\,\exp{\Big(n\big( h(u_0) + \frac{h''(u_0)}{2}\,u_0^2\big)\Big)} \,
\...

1

So, the canonical answer is the q-Lucas theorem, as pointed out in the comments.
This was proved in
Olive, Gloria, Generalized powers, Am. Math. Mon. 72, 619-627 (1965). ZBL0215.07003.

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

co.combinatorics × 7717graph-theory × 1602

nt.number-theory × 803

reference-request × 650

pr.probability × 605

discrete-geometry × 383

gr.group-theory × 351

rt.representation-theory × 349

linear-algebra × 333

algorithms × 231

graph-colorings × 231

permutations × 222

ag.algebraic-geometry × 212

additive-combinatorics × 207

enumerative-combinatorics × 194

computational-complexity × 187

convex-polytopes × 181

matrices × 177

partitions × 172

mg.metric-geometry × 167

binomial-coefficients × 167

polynomials × 166

sequences-and-series × 156

finite-groups × 149

asymptotics × 127