Recent MathOverflow Questions

Hereditary Lindelöfness in $C_p$-spaces

Math Overflow Recent Questions - Thu, 06/14/2018 - 05:20

Let $X$ be a (infinite) separable topological space and consider $C_p(X)$, the space of continuous functions on $X$ endowed with the point-wise convergence topology.

Q. I am looking for topological properties on $X$ which make $C_p(X)$ hereditary Lindelöf.

$$X=?\implies C_p(X)=\textrm{Hereditary Lindelöf}$$

Feasibility Mixed integer Linear programming with quadratic constraints?

Math Overflow Recent Questions - Thu, 06/14/2018 - 04:49

Consider the mixed integer program $$Ax\leq b$$ $$By\leq c$$ $$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer variables of dimension $n$ and $y$ are real variables.

Because of the quadratic conditions this problems is in general $NP$ hard.

Is it possible convert this into exponentially larger mixed linear integer program by blowing up the number of integer variables only to a polynomial in $n$?

The remaining problem will be exponential time solvable as original one and would still be np hard.

Egyptian sums' front corner overflow over selected primes

Math Overflow Recent Questions - Thu, 06/14/2018 - 00:41

The Question

I'll present my first two simple steps toward estimating certain Egyptians sums. I hope that someone (perhaps an expert in Analysis or Analytic Number Theory) will continue and will achieve essential results, possibly even about the baroque (multi perfect) numbers--and this is the challenge of this Question. (See the end of this "step 2" section, before the final comments).

Remark: this post is a continuation of Corner integrals of $\exp$

A pre-approximation integral

The said sums are related to an integral of $\ \exp(-\sum_{k=1}^n x_k)\ $ over the corner

$$ \Delta(n;\ S)\ :=\ \{(x_1\ldots x_n)\in[0;\infty)^n\, : \, \sum_{k=1}^n x_k\le A\} $$

The integral is

$$ I_{n;\ S}\ :=\ \int_{\Delta(n;\ S)} \exp\left(-\sum_{k=1}^n x_k\right)\cdot dx_1\ldots dx_n\,\ = \,\ 1 -\ \sum_{k=0}^{n-1} \frac{S^k}{k!} \cdot e^{-S} $$

A connection with the Egyptian sums over selected primes (step 1)

Let natural numbers $\ p_1\ \ldots\ p_n\ >\ 1$ be pairwise relatively, the main case would be $n$ different primes. They define a lattice

$$ L\ :=\ L(p_1\ldots p_n)\ :=\ (\log(p_1)\!\cdot\!\mathbb Z)\times\ldots \times(\log(p_n)\!\cdot\!\mathbb Z)\ \subseteq\mathbb R^n $$

We want to compute or realistically estimate

$$ \mathbf S(p_1\ldots p_n;\ S)\ :=\ \sum_{(x_1\ldots x_n)\,\in\, L\cap\Delta(n;\ S)} \,\ \frac 1{\prod_{k=1}^n p_k^{f_k}} $$

where $\ x_k\ :=\ f_k\cdot\log(p_k)\ $ for $\ k=1\ldots n$. We may visualize ech of the above fractions attached to the respective lattice point $\ (x_1\!\cdot\!\log(p_1)\ \ldots\ x_n\!\cdot\!\log(p_n)),\ $ as suggested by

$$ \mathbf S(p_1\ldots p_n;\ S)\ := \ \sum_{(x_1\ldots x_n)\,\in\, L\cap\Delta(n;\ S)} \,\ \exp\left(-\sum_{k=1}^n x_k\right) $$

The first approximation and an overflow (step 2)

Let $\ x\ :=\ (x_1\ \ldots\ x_n)\in \mathbb R^n.\ $ Define the respective cell $$ C(x)\ := \prod_{k=1}^n [x_k;\,x_k+\log(p_k)) $$

If $\ x\in L\ $ then $\ C(x)\ $ is called a lattice cell. In general,

$$ \int_{C(x)}\exp\left(-\sum_{k=1}^n t_k\right)\cdot dt_1\ldots dt_n\ = \ \exp\left(-\sum_{k=1}^n x_k\right)\cdot\prod_{k=1}^n \left(1-\frac 1{p_n}\right) $$

This applied to the lattice cells gives:

Theorem

$$ \mathbf S(p_1\ldots p_n;\ S)\ =\ \frac {\int_{\bigcup\{C(x)\,:\,x\in \Delta(n;\ S)\}} \ \exp\left(-\sum_{k=1}^n t_k\right)\cdot dt_1\ldots t_n} {\prod_{k=1}^n\left(1-\frac 1{p_k}\right)} $$

This desired value is approximated by $\ \frac{I_{n;\ S}}{\prod_{k=1}^n\left(1-\frac 1p\right)}.\ $ Of course, $\ \Delta(n;\ S)\ \subseteq \ \bigcup\{C(x)\,:\,x\in \Delta(n;\ S)\}.\ $ Unfortunately, the difference is challengingly annoying

$$ \Omega\,\ :=\,\ \bigcup_{x\in \Delta(n;\ S)} C(x)\ \ \setminus \,\ \Delta(n;\ S) $$

To estimate the overflow (call it an error) $$ E\ :=\ E(p_1\ldots p_N;\ S)\ :=\ \mathbf S(p_1\ldots p_n;\ S) - \frac{I_{n;\ S}}{\prod_{k=1}^n\left(1-\frac 1{p_k}\right)} $$

i.e.

$$ E(p_1\ldots p_N;\ S)\ =\ \frac {\int_E \exp\left(-\sum_{k=1}^n t_k\right)\cdot dt_1\ldots dt_n} {\prod_{k=1}^n\left(1-\frac 1{p_k}\right) } $$

should have implications for Egyptian sums (possibly, also for baroque numbers).

Comments

  1. In the popular case of $\ p_1<\ldots<p_n\ $ being the first (smallest) $n$ primes, the Mertens' formula applies. Instead of its most common form about $\ \prod_{k=1}^n \left(1-\frac 1{p_k}\right)\ $ (as above), the less common upside down version fits here better: $$ \prod_{k=1}^n\frac {p_k}{p_k-1}\ =\ e^\gamma\cdot\log(p_n) + O(1) $$

  2. On the top of the sums and integrals over the corners $\ \Delta(n;\ S),\ $ one could equally often consider their complements $\ [;\infty)^n\ \setminus\ \Delta(n;\ S)\ $ and general trapezoids $\ \Delta(n;\ T) \setminus\ \Delta(n;\ S)$.

The symmetric group theory of natural numbers

Math Overflow Recent Questions - 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

Math Overflow Recent Questions - 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?

Math Overflow Recent Questions - 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?

Math Overflow Recent Questions - 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?

Math Overflow Recent Questions - 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$?

Math Overflow Recent Questions - 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

Math Overflow Recent Questions - 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

Math Overflow Recent Questions - 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

Math Overflow Recent Questions - 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

Math Overflow Recent Questions - 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

Math Overflow Recent Questions - 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?

Math Overflow Recent Questions - 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?

Math Overflow Recent Questions - 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]

Math Overflow Recent Questions - 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]

Math Overflow Recent Questions - 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?

Math Overflow Recent Questions - 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

Math Overflow Recent Questions - Mon, 06/11/2018 - 14:08

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

Pages

Subscribe to curious little things aggregator