Math Overflow Recent Questions

Subscribe to Math Overflow Recent Questions feed
most recent 30 from mathoverflow.net 2018-06-24T03:46:36Z

The symmetric group theory of natural numbers

Wed, 06/13/2018 - 18:39

Sometimes it is not easy to formulate a correct question. Here is a better version of this question (I still do not know if it is optimal, but it is better than the previous one).

We say that a set $X$ of natural numbers is symmetric group definable if there exists a first order formula $\theta$ in the group signature such that a symmetric group $S_n$ satisfies $\theta$ if and only if $n\in X$. Of course finite sets and sets with finite complements are symmetric group definable. It is not completely trivial to find any infinite set of natural numbers with infinite complement which is symmetric group definable. But it is not a difficult exercise to show that the set of numbers $n$ such that either $n$ or $n-1$ is prime is such a set.

Question. Is any of the following sets symmetric group definable?

1) the set of even numbers

2) the set of prime numbers

A more vague question Is there a characterization of the Boolean algebra of symmetric group definable sets?

Update Noam D. Elkies' answer below shows that the Boolean algebra contains many sets. Noah Schweber's answer of the previous question suggests looking at the computational complexity of $X$. Clearly, checking whether $n$ belongs to a symmetric group definable set $X$ takes time at most $(n!)^k$ where $k$ is the number of quantifiers in the corresponding formula $\theta$. So we have a couple of even better questions.

Question 1 Is the converse true, that is every set of numbers recognizable by deterministic a Turing machine in time $\le (n!)^k$ for some $k$ symmetric group definable? Here the size of a number $n$ is $n$ that is we consider the unary representation of natural numbers.

Question 2 Let us replace $S_n$ by, say, $SL_n(\mathbb{F}_2)$ and similarly define $SL_n(\mathbb{F}_2)$-definable sets of numbers. Will the Boolean algebra of all $SL_n(\mathbb{F}_2)$-definable sets coincide with the Boolean algebra of all deterministic polynomial time decidable sets of natural numbers?

Question 3 Can the statements that "Primes are in P" be proved this way?

A few general questions about pre-sheaves and sheaves

Wed, 06/13/2018 - 07:47

I am no specialist in sheaf theory, so I would be glad to get some help regarding the following:

I have a pre-sheaf $F$ of abelian groups above a topological space $X$, and I have found an open cover $\{U_i\}$ of $X$ such that, for any $i$, $F(U_i)$ is a direct sum: $$F(U_i) = \underset{l}{\bigoplus} F^l (U_i),$$ where $F^l$ are pre-sheaves on $X$.

I have the two following questions:

  1. Is it true in general that a direct sum of pre-sheaves (resp. sheaves) of abelian groups is a pre-sheaf (resp. sheaf), or does it have to be a finite sum ? If it is true, how do we define sections and restriction morphisms for general direct sums of pre-sheaves ?
  2. How to prove that the sheafification $F^{\#}$ of $F$ is given by the direct sum: $$F^{\#} = \underset{l}{\bigoplus} F^{l \#},$$ where $F^{l \#}$ is the sheafification of $F^l$ ?

Thanks a lot for your help !

Categorification of monotone maps via tilting modules?

Wed, 06/13/2018 - 03:18

It is well known that for the algebra of $n \times n$-upper triangular matrices over a field the number of tilting modules is equal to the Catalan number $C_n$. This is just the (hereditary) Nakayama algebra with Kupisch series $[n,n-1,...,2,1]$ and can be viewed as the "mother" of all Nakayama algebras with a linear quiver because it has each such algebra as a quotient. The cyclic analogue of this algebra is the Nakayama algebra with Kupisch series $[n,2n-1,2n-2,....,n+2,n+1]$ for $n \geq 2$, which can be viewed as the "mother" of all Nakayama algebras with a cyclic quiver of finite global dimension because it has each such algebra as a quotient. Now let $A$ be this Nakayama algebra with Kupisch series $[n,2n-1,2n-2,....,n+2,n+1]$. This is an algebra with global dimension 2 (while the algebra of upper triangular matrices has global dimension 1).

I wondered what the tilting modules over this algebra are. The problem seems to contain the problem of classifying the tilting modules over the algebra of upper triangular matrices as a special case because the indecomposable modules with projective dimension one in $A$ just behave like modules over the algebra of upper triangular matrices and thus the number of 1-tilting modules of $A$ should be also equal to the Catalan numbers.

The number of tilting modules of $A$ starts with 1,3,10,35,126 and this suggests that the number of tilting modules equals $\binom{2n-1}{n}$ which are the monotone maps $\{1,...,n \} \rightarrow \{1,...,n \}$, see https://oeis.org/A001700.

This leads to the following guess:

There is a natural bijection from the set of monotone maps $\{1,...,n \} \rightarrow \{1,...,n \}$ to the set of tilting modules of $A$.

Note that the monotone maps $f$ with $f(i) \leq i$ are counted by the Catalan numbers (see for example exercise 78. in the book "Catalan numbers" by Richard Stanley) and thus the above bijection (if it exists) should restrict to a bijection between monotone maps $f$ with $f(i) \leq i$ and the 1-tilting modules of $A$ (at least if it is a nice bijection).

I wanted to ask whether there is a quick proof of this guess in case it is true using some advanced tools. I am able to translate the problem into a purely combinatorial problem but it looks very complicated at the moment and maybe there is an easy trick to obtain such a bijection or maybe this is even known.

The combinatorial translation gives the problem where $n$ points (corresponding to the indecomposable summands of the basic tilting module) are drawn into two triangles (whose points correspond to the 2-rigid indecomposable modules in the Auslander-Reiten quiver of the algebra). There is one bigger triangle with $\frac{n(n+1)}{2}$ points and one smaller triangle with $\frac{n(n-1)}{2}$ points so that both triangles have together $n^2$ points. Here the tilting modules for $n=3$ (maybe someone can see how they correspond to monotone sequences?): https://www.docdroid.net/YwBhi0k/monotonetilting.pdf

Here the configurations where the red market points only occur in the smaller triangle or on the leftmost boundary of the bigger triangle count the 1-tilting modules so that for n=3 we get 5 1-tilting modules.

Is Lenstra's Mixed Integer Linear Program essentially ILP with Khachiyan oracle?

Mon, 06/11/2018 - 22:47

In his paper 'https://people.csail.mit.edu/rrw/presentations/Lenstra81.pdf' Lenstra says in section $5$ that $n$ integer variable, $k-n$ real variable and $m$ constraint Mixed Linear Integer Program is in $C_n\mathsf{poly}(k,n,m)$ time where $C_n$ depends on $n$.

On reading the paper closely he says

What exactly happens here?

Is following interpretation correct?

Lenstra's MILP is actually two different modules

  1. ILP module

  2. LP module

ILP module calls the LP module.

That is does Lenstra actually prove $MILP$ is in $ILP$ with an oracle to Khachiyan's algorithm. That is $MILP$ is in $ILP$ with a $P$ oracle.

Since $ILP$ here is fixed parameter in integer variables we have that $MILP$ is in $P^P=P$ since fixed parameter $ILP$ is in $P$. Does it sound reasonable to what Lenstra does?

If my interpretation is wrong then what exactly does he do? Is it possible to some expert to weigh in on why and what makes his $MILP$ work?

Are there any advanced level math audiobooks?

Mon, 06/11/2018 - 19:40

I am aware of a few interesting math podcasts but haven’t come across any interesting advanced math audiobook. Are there some?

Does $n^2$ divide $\det\left[\left(\frac{i^2+2ij+3j^2}n\right)\right]_{1\le i,j\le n-1}$ for each odd integer $n>3$?

Mon, 06/11/2018 - 19:29

For any odd integer $n>1$ and integers $c$ and $d$, define $$(c,d)_n:=\det\left[\left(\frac{i^2+cij+dj^2}n\right)\right]_{1\le i,j\le n-1},$$ where $(\frac{\cdot}n)$ is the Jacobi symbol. It is easy to show that $(c,d)_n=0$ if $(\frac dn)=-1.$

QUESTION: Does $n^2$ divide $(2,3)_n$ for each odd integer $n>3$?

My computation led me to conjecture that $n^2\mid (2,3)_n$ for any odd integer $n>3$ and also $n^2\mid (6,15)_n$ for any odd integer $n>5$.

For any positive integer $n\equiv\pm5\pmod{12}$, we have $(\frac 3n)=-1$ and hence $(2,3)_n=0$. Also, I observe that $(2,3)_n=0$ if $n>3$ and $n\equiv 3\pmod 6$. But I don't see why $(2,3)\equiv0\pmod{n^2}$ for each positive integer $n\equiv\pm1\pmod{12}$. Note that $$\frac{(2,3)_{11}}{11^2}=-2^3\ \ \text{and}\ \ \frac{(2,3)_{37}}{37^2}=2^{44}\times467^2.$$

I also have some other questions concerning $(c,d)_n$. For example, I conjecture that $(6,1)_n=0$ for any positive integer $n\equiv 3\pmod4$. For more such questions, one may consult my preprint On some determinants with Legendre symbol entries.

Any ideas helpful to the question ?

p-adic topology

Mon, 06/11/2018 - 19:27

I struggle to see why if we take a finite extension $K$ of $\mathbb{Q}_p$, the group of units $U_K$ of the ring of integers of $O_K$ is open for the $p$-adic topology. For me we have $U_K= \lbrace v_K(x)=0,~ x \in K \rbrace $ but I don't see why that mean that this set is open.

parallel tensor fields and holonomy group

Mon, 06/11/2018 - 18:51

According to Berger, I can classify the holonomy group into some fixed groups (as subgroups). There is also a theorem (picture) that states a relationship with tensor fields. I would like to know, how many parallel tensors there are (and if they depend or not in the holonomy group)theorem that relates invariance and tensor fields

Modular arithmetic and elementary symmetric functions

Mon, 06/11/2018 - 18:41

Denote the elementary symmetric functions in $n$ variables by $e_k(x_1, x_2,\dots, x_n)$. In the special case $x_j=j$, simply write $e_k(n)$ for $e_k(1, 2, \dots, n)$. Next, define the sequence
$$a_{+}(n)=\sum_{k\geq0}(-1)^ke_{2k}(n).$$

I am interested in the following:

Question. If $\lambda_n=\frac{3-(-1)^{\lfloor n/2\rfloor}}2$, then is it true that We have $a_{+}(n)\equiv\lambda_{n+1}\mod3?$

A non integrable distribution arising from a Lie algebra of vector fields

Mon, 06/11/2018 - 17:43

Is there an example of a $n$ dimensional manifold $M$ and a natural number $k<n$ with a Lie subalgebra $L$ of $\chi^{\infty}(M)$ with the following property:

For every $x\in M$ the space $\{V_x \in T_x M\mid V\in L\} $ is a $k$ dimensional vector space $D_x$ but the distribution $D$ consisting of all $D_x,\;x\in M$ is not an integrable distribution.

In the other word we search for a non integrable distribution $D$ of a manifold and a Lie algebra $L$ of vector fields such that $L$ is $D$-ample where $D$- ample means that the evaluation $L_x$ of $L$ at every point $x$ is equal to $D_x$.

A member of a Jacobian pair having degree a product of three primes

Mon, 06/11/2018 - 17:06

Let $p=p(x,y),q=q(x,y) \in \mathbb{C}[x,y]$ be a Jacobian pair, namely, $p_xq_y-p_yq_x \in \mathbb{C}^*$. Denote $a:= \deg(p)$ and $b:= \deg(q)$, where $\deg()$ denotes the total degree ($(1,1)$-degree).

There are several nice results about when a Jacobian pair is an automorphic pair (= $f: (x,y) \mapsto (p,q)$ is an automorphism of $\mathbb{C}[x,y]$) involving $a$ and $b$.

For example, each of the following conditions implies that $f$ is an automorphism:

(1) $\gcd(a,b)=1$; Magnus.

(2) $\gcd(a,b) \leq 2$; Nakai-Baba

(3) $\gcd(a,b)=P$, $P$ is a prime number; Appelgate-Onishi-Nagata.

(4) $a=PQ$, $\{P,Q\}$ are prime numbers; Nowicki.

Is there any progress about the following two cases:

(3)' $\gcd(a,b)=PQ$, $\{P,Q\}$ are prime numbers.

(4)' $a=PQR$, $\{P,Q,R\}$ are prime numbers.

Remarks: (I) I can prove that $(4)'$ implies $(3)'$ (as well as that $(4)$ implies $(3)$).

(II) Probably it is possible to replace $\mathbb{C}$ by any algebraically closed field of characteristic zero or even by any field of characteristic zero, but I do not mind to work over $\mathbb{C}$.

Any hints and comments are welcome!

Is this condition equivalent to being a matroid quotient?

Mon, 06/11/2018 - 16:24

Here is the condition, which arose in contemplating polytopes associated to matroid quotients:

Let $M$ and $N$ be matroids on $E$. If $X \subseteq Y \subseteq E$ such that $X$ is indepedent in $N$ and $Y$ is spanning in $M$, then $X$ is independent in $M$ and $Y$ is spanning in $N$.

If $M \to N$ is a matroid quotient, then this condition does hold.

Proof: First, recall that $M \to N$ is a matroid quotient if and only if the following exchange condition holds: if $B_N$ is a basis of $N$, $B_M$ is a basis of $M$, and $i \in B_N - B_M$, then there exists $j \in B_M - B_N$ such that $B_N-i+j$ and $B_M-j+i$ are both bases. This follows since the fundamental cocircuit of $(B_N,i)$ and fundamental circuit of $(B_M,i)$ must intersect in more than one element.

If $X\subseteq Y \subseteq E$ such that $X$ is independent in $N$ and $Y$ is spanning in $M$, then there is a basis $B_N \supseteq X$ of $N$ and a basis $B_M \subseteq Y$ of $M$, respectively. To show $Y$ is spanning in $N$: Let $B \supset X$ be a basis of $N$ such that $|B-Y|$ is minimized. Then if $x \in B - Y$, $x$ is not in $B_M$, and the above exchange condition gives a $y \in B_M - B$ such that $B - x + y$ is a basis of $N$, which contradicts our construction of $B$. Hence, $B \subseteq Y$ and so $Y$ is spanning in $N$. The argument for $X$ is dual.

The proof of this condition only uses one half of the quotient basis exchange condition at a time. However, for a single matroid, the strong and weak basis exchange conditions are equivalent, which gives me hope (although the proof of this equivalence does not seem to generalize to this problem).

Is there a physical/geometric proof for L^2 boundedness of Bourgain's maximal function along the squares?

Mon, 06/11/2018 - 16:17

One problem that has bugged me for some time (though I only seriously thought about it for a month several years ago) is to give a physical proof of the L^2 boundedness of Bourgain maximal function for averages along the squares.

To be precise, define the averages: for a function $f: \mathbb{Z} \to \mathbb{C}$, let $$ A_Nf(x) := N^{-1} \sum_{n=1}^N f(x-n) $$ and the maximal function $$ Mf(x) := \sup_{N \in \mathbb{N}} |A_Nf(x)| $$ for $x \in \mathbb{Z}$.

Question: Without resorting to the circle method, can one prove that $M: \ell^2(\mathbb{Z}) \to \ell^2(\mathbb{Z})$?

In particular, I suspect that there a physical proof analogous to the proofs for $L^2$ boundedness of Stein's spherical maximal function theorem as sketched out by Laba here: https://ilaba.wordpress.com/2009/05/23/bourgains-circular-maximal-theorem-an-exposition/ or as in Schlag's work: https://math.uchicago.edu/~schlag/papers/dukecircles.pdf In particular, I am happy with a physical proof of restricted weak-type $L^2$ boundedness.

My suspicion is that Bourgain's proof, which uses the circle method, suggests that we should consider understand what happens on arithmetic progressions, decompose the characteristic function of a set into how arithmetic progressions and combine them in some way. However I could not see how to successfully deploy this strategy...

sigma algebra generated by countable product [on hold]

Mon, 06/11/2018 - 16:00

Suppose that $C \in \sigma(\{A_{n} \times B_{n} : n=1,2,...\})$ and $C_{x} = \{y \in Y: (x,y) \in C\}$. Proof that if $x_{1}$ and $x_{2}$ belong to the same $A_{n}$ then $C_{x_{1}} = C_{x_{2}}$

By graphing the function f(x) = (cos 2x − cos x)/x2 estimate the value of lim x → 0 f(x) [on hold]

Mon, 06/11/2018 - 16:00

(a) By graphing the function f(x) = (cos 2x − cos x)/x2 and zooming in toward the point where the graph crosses the y-axis, estimate the value of lim x → 0 f(x).

(b) Check your answer in part (a) by evaluating f(x) for values of x that approach 0. (Round your answers to six decimal places.) f(0.1) =
f(0.01) =
f(0.001) =
f(0.0001) =
f(−0.1) =
f(−0.01) =
f(−0.001) =
f(−0.0001) =
lim x→0 f(x) =

To evaluate a monotonic function over a convex set, does it suffice to consider the vertices?

Mon, 06/11/2018 - 14:15

I got a function

$y = f(x)$ where $y \in \mathbb{R}$ and $x \in P \subset \mathbb{R}^3$ and $P$ is a convex polytope.

I want to find the minimum and maximum of $y$ provided that $x \in P$.

I can show that $f$ is monotonic over the set $P$, i.e. the elements of the gradient do not change their signs.

My question: For the case that $P$ is an interval, I can evaluate $f$ at the vertices of this interval to find the minimum and maximum. Is the same true if $P$ is a convex polytope?

Second order system of ODE

Mon, 06/11/2018 - 14:08

What method can be used to solve following second order system of ODE? Second order system of ODE

Singularities of quotient of vector bundles by lattice

Mon, 06/11/2018 - 13:39

Let $V$ be a vector bundle on the unit disc $\Delta$, $W \subset V$ be a sub-bundle and $H \subset V$ a sub-lattice of constant rank, in the sense that $H$ is a local system on $\Delta$, contained in $V$ and for all $t \in \Delta$, the fiber $H_t$ is a lattice. Suppose that for all $t \not= 0$, $H_t \cap W_t=0$ and $H_0 \cap W_0 \cong \mathbb{Z}$. Then, what is the singularity of the quotient $(V/W)/(H/H \cap W)$? Is it a complex manifold or an orbifold or worse? Any reference/hint will be most welcome.

Citations graphs what is known?

Mon, 06/11/2018 - 13:35

There have been much research related to webgraphs and social graphs. They can be thought of a kind of random graphs, but the point is that they are different from the well-known Erdős–Rényi model.

Question: consider citatations graphs in some field of research are there any known mathematical models for them ? Emperical observations on mathematical properties of such graphs (similar to mentioned below) ?

Definition: Citation graphs are graphs with vertices given by publications and edges by citations.

Here are main properties of webgraphs, I wonder about something similar for citation graphs.

1) Diameter is quite small (~6) or Law of Six degrees of separation

2) "Sparsity" - adjacency matrix is sparse matrix,

3) Power law of distribution of degrees of vertices: C/d^(2.1) - number of vertices with "d" edges

And there is suggestion for the model how webgraphs are growing: Barabási–Albert model, with the key idea of Preferential attachment:

Preferential attachment means that the more connected a node is, the more likely it is to receive new links. Nodes with higher degree have stronger ability to grab links added to the network. Intuitively, the preferential attachment can be understood if we think in terms of social networks connecting people. Here a link from A to B means that person A "knows" or "is acquainted with" person B. Heavily linked nodes represent well-known people with lots of relations.

See e.g. https://www.mccme.ru/free-books/dubna/raigor-4.pdf

What are the LCA groups that are the Pontryagin dual of a locally profinite abelian group?

Mon, 06/11/2018 - 12:23

For certain subcategories of LCA groups, we have nice descriptions of the dual category under Pontryagin duality (all groups are implicitly assumed to be abelian):
finite groups $\leftrightarrow$ finite groups
discrete groups $\leftrightarrow$ compact groups
discrete torsion groups $\leftrightarrow$ profinite groups
discrete groups where each element is annhilated by some power of $p$ $\leftrightarrow$ pro $p$-groups
etc.

So I was wondering if we have a similar description of the Pontryagin dual of the category of abelian locally profinite groups, i.e. locally compact totally disconnected groups. Since locally profinite groups include discrete groups and profinite groups, the dual category will need to include discrete torsion groups and compact groups. Is there more we can say?

Pages