Math Overflow Recent Questions


Proof of an inequality $s_m(n) \le f_m(n)$

Tue, 07/17/2018 - 01:26

For fixed $m = 0, 1, 2, ...$ $$f_m(k) = \prod_{j=1}^{m}(k+j).$$ Some examples of $f_m(k)$ are as following: $$f_0(k) = 1, \quad f_1(k) = (k+1), \quad f_2(k) = (k+1)(k+2).$$

The $s_m(n)$ is defined as following: $$s_m(n) = \sin\left(\frac{t}{2}\right)\sum_{k=0}^nf_m(k)\sin(k+0.5)t,\qquad t\in[0,\pi].$$

The $s_m(n)$ can also be defined as following: $$s_m(n) = \sum_{j=0}^n\frac{(-4)^j}{(2j+1)!}\left(\sum_{k=j}^n\frac{f_m(k)(2k+1)(k+j)!}{(k-j)!}\right)x^{2j+2},\qquad x\in[0,1].$$

I want to prove $$|s_m(n)| \le f_m(n), \forall x ~or ~t$$

I am sure the inequality holds but I am unable to prove it. I used MATLAB and verified the inequality for some values of $m$ and $n$ as presented below:

\begin{array}{ccccccccc} n & \max(s_0(n)) & f_0(n) & \max(s_1(n)) & f_1(n) & \max(s_2(n))& f_2(n) & \max(s_3(n)) & f_3(n)\\ 0 & 1.00 & 1 & 1.00 & 1 & 2.00 & 2 & 6.00 & 6 \\ 1 & 1.00 & 1 & 1.53 & 2 & 4.17 & 6 & 18.00 & 24 \\ 2 & 1.00 & 1 & 2.07 & 3 & 8.00 & 12 & 42.00 & 60 \\ 3 & 1.00 & 1 & 2.60 & 4 & 12.46 & 20 & 78.30 & 120 \\ 4 & 1.00 & 1 & 3.13 & 5 & 18.03 & 30 & 132.00 & 210 \end{array}

Any help will be greatly appreciated.

PS: Please refer to this question. I asked for inductive proof so that I could use induction steps in the above inequality. But I did not get one.

Integral representations of finite groups and lattice point geometry

Mon, 07/16/2018 - 13:39

This contains both a reference request, and a specific problem. Let $K$ be a finite group, and let $\theta: K \to {\rm GL}(d,{\bf Z})$ be a (faithful) group representation over the integers. Consider the following property of $\theta(K)$ (not merely of $\theta$): there exists a finite subset $S$ of $ H = {\bf Z}^d$ such that

(0) $0 \in S$;

(i) $\cup_{n \geq 1} nS = H$ [here $nS$ means the set of sums of $n$ elements of $S$];

(ii) $S$ is $\theta$-invariant;

(iii) if we set $C$ to be the convex hull (in Euclidean space, ${\bf R}^d$), of $S$, then $0$ belongs to the interior of $C$ and the natural action of $\theta$ on $C$ is transitive on the set of facets of $C$ [a facet is a face of codimension one; the transitivity condition is that every facet can be moved to all other facets by elements of $\theta(K)$];

(iv) for each facet $F$ of $C$, let $S_F =S \cap {\rm cvx } \{F,0\}$; we require that $S_F$ generate $ H$ as a group, and $C_F:=\cup_{n\geq 1} nS_F$ is a simplicial cone.

Despite this ridiculously complicated set of conditions, there are plenty of natural examples.

Example 1 Take $K ={\bf Z}_2^d$ acting as the group of diagonal $\pm1$ matrices on ${\bf Z}^d$, and set $S = \{0; \pm e_i \}$ where the $e_i$ vary over the standard basis. Then $C$ is just a $d$-dimensional version of the octohedron, and the facets correspond to the intersection with the orthants, and it is clear that $\theta$ acts transitively on them. The simplicial condition is obvious. [Here, $K$ acts far from transitively on the extreme points of $C$, but this does not matter.]

Example 2 Let $K = \cal S_{d+1}$, the full permutation group on $d+1$ symbols, or any subgroup which acts transitively on the symbols. Then $K$ acts on ${\bf Z}^{d+1}$ by permuting the standard basis elements, and leaves $v= (1,1,\dots, 1)$ invariant. So we obtain the quotient action of $K$ on ${\bf Z}^{d+1}/v{\bf Z} $ identified with ${\bf Z}^{d}$. With $S$ being the orbit of $e_1$ in ${\bf Z}^{d}$ together with $0$, that is, $S = \{0, e_1, e_2,\dots, e_d; -\sum e_i \}$, then it is easy to see that $C$ is a simplex, and the simplicial condition holds, and transitivity is obvious.

Example 3 Let $d = 2$, and let $\theta : K \to {\rm GL}(2,{\bf Z})$ be one to one (faithful). Provided $K$ has more than two elements, then an $S$ satisfying (0--iv) exists.

For the last, the only group which requires more than a few sentences is $K = C_2 \times C_2$, for which there exist two outer conjugacy classes of faithful representions on ${\bf Z}^2$.

The existence of a set $S$ with the properties (0--iv) is obviously an invariant of the integral representation $\theta$ of $K$, in fact an outer invariant: it is an invariant of the image of $K$, $\theta(K) \subset {\rm GL}(d,{\bf Z}^{d})$. This type of thing (using integral geometry to obtain invariants for integral representations) must have been done before.

First question [finally] A reference request for analyzing integral representations of finite groups by lattice point geometry.

Second question Are there more examples than the ones I described, or more generally, can useful necessary/sufficient conditions be derived for the existence of such a set $S$?

Apparently, it is necessary that the trivial representation not be a subrepresentation of $\theta$, and multiplicities should be avoided.

The motivation comes from studying random walks and suitable weight functions on the semidirect product groups ${\bf Z}^{d}\times_{\theta} K$; when such an $S$ exists, the random walks (weight functions) have nicer properties than when no such $S$ exists.

A translation between formal and rigid geometry

Mon, 07/16/2018 - 09:31

The following lemma is in Bosch's book "Lectures on Formal and rigid geometry" p198.

Lemma Let $K$ be a non-archimedean field and $R$ its valuation ring. Let $X= \mathrm{Spf}A$ be an affine admissible formal $R$ scheme. Then there are canonical bijections between (1) the set of non-open prime ideals $\mathfrak{p}\subset A$ with $\dim A/\mathfrak p =1$ and (2) the set of maximal ideals in $A\otimes_RK$.

Now let's look at a easy case: $A=R\langle \zeta_1,\dots,\zeta_n\rangle$. Then $A\otimes_RK$ is simply the Tate algebra $T_n:=T_n(K)$. Then we know the set of maximal ideals in $T_n$ can be described by the points of the unit ball $\mathbb B^n(K)$(assume $K$ is algebraically closed): $\mathfrak{m}_x=\{f\in T_n\mid f(x)=0\}$ The question is that what the prime ideal does $\mathfrak m_x$ correspond by the above lemma?

Quadratic integer program over a sphere

Mon, 07/16/2018 - 03:26

Given vector $a \in \mathbb{R}^K$ and symmetric and positive definite matrix $M \in \mathbb{R}^{K \times K}$,

\begin{align} \underset{\vec{x}}{\text{minimize}}\quad &(\vec{x}-a)^\dagger M(\vec{x}-a)\\ \text{subject to}\quad & \| \vec{x} \|^2 = n \\ & \vec{x} \in \mathbb{Z}^K \end{align}

Has any work been done on this? My thinking is that the solution can somehow be approximated with the LLL algorithm.

Reference request: explicit equivariant localization formula on toric complete intersections

Sun, 07/15/2018 - 06:51

This post is about an equivariant integration formula in a famous paper by Alexander Givental, where the author presented the formula without proof or reference. It turns equivariant localization into calculation of residues I am trying to combine it with global residue theorem to derive some vanishing result of some invariant.

$$ \int_X f(p,\lambda)=\sum_{\alpha}Res_{\alpha}\frac{f(p,\lambda)dp_1\wedge\cdots\wedge dp_k}{u_1(p,\lambda)\cdots u_n(p,\lambda)} $$ where $X$ is a toric symplectic variety, $p_k$ forms base of $H^2(X)$ (the Picard group) and $u_i(p,\lambda)=\sum_ip_im_{ij}-\lambda_j$, where $m_{ij}$ is a integer matrix describing how $p_i$ span all the invariant divisors and $\lambda_i$ is the ordinary equivariant index for torus action. The RHS sums over fixed point or pole specified by some of the $u_i=0$.

This paper is hard to read because I am not an expert on symplectic geometry but I really need to re-derive this explicit formula. Maybe some experts could kindly provide me some hints or references and any other discussion is welcomed. Thanks in advance.

Testing whether a quiver algebra is cellular with a computer

Sun, 07/15/2018 - 06:25

With a friend I made a program in the GAP-package QPA to check whether a given finite dimensional quiver algebra is quasi-hereditary. It is very slow since it has to go through all permutations of points in the quiver but in principle it works by using just linear algebra. Now a similar class as quasi-hereditary algebras are cellular algebras: A cellular algebra is quasi-hereditary iff it has finite global dimension.

Question: Is it possible to have a programm in QPA that checks whether a given finite dimensional quiver algebra is cellular (by using given commands that preferably only use linear algebra)?

I have no real experience with cellular algebras and the definitions make it look like the answer is no. But maybe there is an equivalent definition of cellular algebras that makes such a QPA-program easy?

representation of prime numbers

Sun, 07/15/2018 - 06:20

We know that primes of the form $p=4k+1$ can be written as sum of two squares, i.e., $p=x^2+y^2$ (uniquely iff $0<x<y$). However, this expression holds for composite numbers that all of the prime factors are of the form $4k+1$, or if they have prime factors of the form $4k+3$, these factors are of even power.

I am looking for some expression to represent prime numbers of the form $p=4k+1$ such that it does not hold for composite numbers? Is it possible to have such expression?

P.S.: If there are some conditions (not necessarily expressing as polynomials) that determine such prime numbers would be desirable.

Thank you.

Surjectivity of norm map on subspaces of finite fields

Sun, 07/15/2018 - 05:52

It is basic that the norm map $N:\mathbf{F}_{q^n}^* \to \mathbf{F}_q^*$ is surjective for finite fields. In fact $N(x) = x^{(q^n-1)/(q-1)}$. How well does this simple fact extend to subspaces?

A basic example is an intermediate extension $\mathbf{F}_{q^d}$. On $\mathbf{F}_{q^d}^*$ we have $$N(x) = \left(x^{(q^d-1)/(q-1)}\right)^{(q^n-1)/(q^d-1)} = \left(x^{(q^d-1)/(q-1)}\right)^{n/d}$$ since the term in the brackets is in $\mathbf{F}_q^*$ and $(q^n-1)/(q^d-1) \equiv n/d \pmod {q-1}$. So $N$ is surjective on $\mathbf{F}_{q^d}^*$ if and only if $(n/d, q-1) = 1$. In particular $N$ fails to be surjective on a subspace of dimension $n/2$ whenever $n$ is even and $(n/2, q-1) > 1$.

As a sort of converse note that if $(n,q-1)=1$ then $N$ is surjective on every one-dimensional subspace.

Is it true that if $V \leq \mathbf{F}_{q^n}$ is a $\mathbf{F}_q$-rational subspace of dimension $>n/2$ then $N$ is surjective on $V$?

Equivalently, if $\dim_{\mathbf{F}_q} V > n/2$, can we always find $x^{q-1} \in V$?

irreducible component of support of function

Sun, 07/15/2018 - 02:49

Vakil gives two equivalent definitions of associated points in his "Rising Sea":

  1. a prime ideal $p$ of a ring $A$ is called an associated prime for module $M$ if it is the annihilator of an element $ m \in M$, i.e. $p = \mathrm{Ann}(m) $
  2. a point p in $\mathrm{Spec} A$ is called an associated point for module $M$ if there is an element $ m \in M$ such that $p$ is a generic point of $\mathrm{Supp } \text{ }m$

Where $A$ is a Noetherian, $M$ is finite generated over A.

Vakil asks readers to check this equivalence, and he gives a hint:

if $p$ is an associated point, then there is an element $m$ with Support $\bar{p}$

If I prove this then I finish the exercise, but I can't.

What is the expected value of n? [on hold]

Sun, 07/15/2018 - 01:52

• A special die is designed with n faces, enumerated 1 through n with all faces being equally likely. If X is the observed number when this die is thrown, what is the expected value of X? [C]
(a) $\frac n2+1$
(b) $\frac n2$
(c) $\frac{n+1}2$
(d) $\frac{n−1}2$
Why is the answer c correct? I know that it is a discrete uniform distribution.

Reference request: Bipartite symmetric graphs are hamiltonian

Sun, 07/15/2018 - 01:23

Does anyone know whether bipartite symmetric graphs are hamiltonian? I'm not sure whether anyone have proved it before, but a nonhamiltonian symmetric bipartite graph would lead to a counterexample to the Lovasz conjecture. I would appreciate any references or ideas.

Does there exist a Lebesgue nonmeasurable set $E$ in $\mathbb{R}$ satisfies that $E\cap A$ is a Borel null set for every Borel null set $A$?

Sun, 07/15/2018 - 00:42

Let $\mathcal{B}_{\mathbb{R}}$ be the Borel $\sigma$-algebra on $\mathbb{R}$ and $\mu_L$ be the Lebesgue measure on $\mathbb{R}$.

Define a new $\sigma$-algebra $\mathcal{B}_0$ as follows: $$\mathcal{B}_0=\{A\in \mathcal{B}_{\mathbb{R}}:\mu_L(E)=0\ \text{or}\ +\infty\}.$$ I want to prove that the family of all locally measurable sets of the measure space $(\mathbb{R},\mathcal{B}_0,\mu_L|_{\mathcal{B}_0})$, that is, $$\{E\subset \mathbb{R}:E\cap A\in \mathcal{B}_0\ \text{for all $A\in \mathcal{B}_0$ such that $\mu_L(A)<\infty$}\}$$ is not the family of all subsets of $\mathbb{R}$.

So I want to ask whether there exists a Lebesgue nonmeasurable set $E$ in $\mathbb{R}$ satisfies that $E\cap A$ is a Borel null set for every Borel null set $A$.

General solution for first-order difference equation

Sat, 07/14/2018 - 22:48

I have the following first-order difference equation

$$y_{t} = \frac{x_{t}}{1-\rho L} + \epsilon_{t}$$

where $L$ denotes the backshift operator, i.e., $L(x_{t}) = x_{t-1}$. I can obtain a solution to this difference equation heuristically, but I am wondering if there is a general procedure. A solution (the solution?) is

$$y_{t} = \sum_{i = 0}^{\infty} \rho^{i}X_{t-i} + \epsilon_{t}$$

I looked in Goldberger's text and couldn't find it there. Any reference is appreciated also. Thanks.

How to visualize a Witt vector?

Sat, 07/14/2018 - 22:24

As the question title asks for, how do others "visualize" Witt vectors? I just think of them as algebraic creatures. Bonus points for pictures.

What are the internal categories in an endofunctor category

Sat, 07/14/2018 - 17:53

Take a category $C$, and take all endofunctors of $C$, so the set $E= \{ M| M: C \rightarrow C \}$. $E$ forms the objects of a category with morphisms given by all natural transformations $\mu : M \rightarrow N$ for $M,N \in E$. Let $\mathcal{C}$ be the endofunctor category as defined. What are the internal categories in $\mathcal{C}$?

Further suppose $C$ is a symmetric monoidal dagger category, in this case, what are the internal categories in $\mathcal{C}$?

Relation between coefficients of expansions

Sat, 07/14/2018 - 16:08

Related to Relations between coefficients of expansions of a rational function at 0 and infinity

I commented at the linked question that the question seemed less about what happened "at infinity", and more about what happened "away from zero". And to some extent, the answer confirmed it by discussing the rank of (the biinfinite matrix corresponding to) the biinfinite sequence - which seems to be the degree of the rational function "away from zero and infinity". This is related to the functions $t$ and $t^{-1}$ on $\mathbb{P}^1$; they are the unique functions with a single zero and single pole at $0$ and $\infty$, or vice versa.

So that brings up a corresponding question:

Are there similar algebraic relations that could be made between the expressions of a rational function $f(t)$ when it is expressed as $A(t), B(t) \in F((t))$ such that $f(t) = A(t), f(t - c) = B(t)$ for some constant $c$?

This isn't quite a generalization of the original question, but gets into another interesting situation - when the zeroes don't match, but the poles do. More generally, we can separate the zeroes as well, leading to:

Are there similar algebraic relations that could be made between $A(t), B(t) \in F((t))$ such that $f(t) = A(t), B(t) = f(\frac{at + b}{ct + d})$?

As in the above question, there is no expectation of a finite algebraic relation. Instead, I'm hoping for a series of "loosening" conditions (similar to the conditions that the biinfinite matrix be rank $n$ for some $n \in \mathbb{Z})$, though I would expect that more than $1$ parameter would be necessary.

Description of (completely) bounded operator

Sat, 07/14/2018 - 16:04

I am somewhat a beginner in the field of operator algebras and was wondering about the following:

Let $T$ be a linear map between the space of bounded operators $B(H)$ on some Hilbert space and $S$ a map between the space of trace-class operators that we denote by $N(H)$ in the sequel.

Then, one defines maps $T_n: M_n(B(H)) \rightarrow M_n(B(H))$ by $$T_n((a_{ij})):=(T(a_{ij}))$$

Then, $T$ is completely bounded if and only if $\sup_n \left\lVert T_n \right\rVert< \infty.$

And analogously for $S.$

I would like to know whether a map $T$ is completely bounded if and only if $$\left\lVert T \otimes \operatorname{id}_{X} \right\rVert< \infty$$ or in case of $S$ whether complete boundedness is equivalent to $$\left\lVert S \otimes \operatorname{id}_{X} \right\rVert< \infty$$

for some $X$?

For $T$ I think I found a reference on math.stackexchange saying that $X=B(K)$ works for any infinite-dimensional Hilbert space $K$ (nothing on whether $K$ needs to be separable discussed in this thread.) This should imply that $X=N(H)$ works for $S$ as well.

Assuming this to be true, I am wondering about two things now:

1.)Assume I can take $X=B(H)$ for $T$ and $X=N(H)$ for $S$, then $T \otimes \operatorname{id}_{B(H)}$ is a map from $B(H) \otimes B(H)$ into itself. Can the space $B(H) \otimes B(H)$ be identified with $B(H \otimes H)$?- I assume that by a duality argument this would be equivalent to asking whether $N(H) \otimes N(H)$ is isomorphic to $N(H\otimes H)$.

2.) Are there any other choices of $X$ allowed in the above two examples?

Is this partition problem strongly NP-complete?

Sat, 07/14/2018 - 15:46

Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the fixed-point free GA problem is NP-complete.

Partition problem is weakly NP-complete problem since it has pseudo-polynomial time algorithm. I am interested in variants that are strongly NP-complete.

Here is a variant of partition problem:

Restricted partition problem

Input: Set $S$ of $2N$ integers, and a collection of pairs $P$ from $S$

Query: Is there a partition of $S$ into two equal cardinality parts $A$ and $S-A$ such that both parts have the same sum and no pair in $P$ has both elements in one side of the partition?

Is this variant of partition problem NP-complete in the strong sense?

Indecomposable ordinals and pseudointersection

Sat, 07/14/2018 - 14:38

Is the following claim correct (Chapter 13 before Theorem 87 of Todorcevic's book: Notes on forcing axioms): Let $\alpha$ be an infinite countable indecomposable ordinal and $U$ be an uniform ultrafilter on $\alpha$ (namely elements in $U$ have order type $\alpha$). Then for any collection $\{B_i\in U: i<\mathfrak{m}\}$ it is true that there exists $B\subset \alpha$ of order type $\alpha$ such that $B-B_i$ is finite for all $i<\mathfrak{m}$. Here $\mathfrak{m}$ is the least cardinal such that Martin's Axiom holds below $\mathfrak{m}$ (i.e. meeting any $\beta$ many dense sets for any $\beta<\mathfrak{m}$).

In fact, it will be interesting to know if this is true at all for countable collection $\{B_i: i<\omega\}$.

It is proved there that the statement is true if we relax the conclusion asking only $B-B_i$ to be bounded in $B$. Any thoughts?

Factoring x15−1 into irreducible polynomials over GF(3) [on hold]

Sat, 07/14/2018 - 14:19

Factoring x^15−1 into irreducible polynomials over GF(3) How can i find this? Thanks in advance.