User knot - MathOverflow

Maximal chain of 1s in binary strings

2013-03-28T11:10:42Z

Let $S$ be the set of $2^n$ binary $n$-bit strings. For every $x\in S$, let $f(x)$ is the maximal chain of bits 1 in $x$. So Can we find a good upper bound of $$F(n)=\frac{\sum_{x\in S}f(x)}{2^n}$$ Of course, $O(1)\le F(n) \le O(n)$. I think the upper bound is a constant or $O(\log n)$. Can anyone help me?

Homogeneous ideal and its system of generators

2012-10-06T02:47:50Z

Let $I$ be a homogeneous ideal in a graded commutative ring $R$, $S$ be its minimal system of generators.

What is the conclusion that we can say about the element in $S$ ? Is the cardinality of $S$ uniquely determined by $I$ ?

In the book Commutative ring theory of Matsumura, theorem 2.3, page 8 there is a theorem for local ring which we can deduce that the number of generator is unique. So, is there a version of that theorem for the graded ring ?

What about the degree of generator in $S$ ?

Combinatorial Inequality

2013-02-15T22:12:47Z

Consider a set of $2^n-1$ non negative integers $S= ${$ a_{i,j}|1\le i\le n; 1\le j\le 2^{i-1} $} such that:

\begin{align}{} 1.\ \ &a_{i,j}\le 2^{n+1-i} \\ 2.\ \ &a_{i,j}\le a_{i-1,j} \\ 3.\ \ &a_{1,1}+\sum_{i=2}^n\left(\sum_{j=2^{i-2}+1}^{2^{i-1}}{a_{i,j}}\right)\le 2^n \end{align} Prove that: $$\sum_{S}a_{i,j}\le k2^n$$ in which $k$ is a constant number.

On the paper "On the asymptotic linearity of Castelnuovo-Mumford regularity"

2012-11-03T16:44:44Z

I have posted this question on MSE, however it seems not to be interested by member there, so I decided to post it here. I am sorry if you feel it is not appropriate for MO.

I am now reading the paper on Castelnuovo-Mumford regularity of Ngo Viet Trung and Hsin-Ju Wang, which can be found here

In this paper, the authors gave the concept of flat extension of ring, and in my opinion, they gave an example of it (in the lemma 1.2):

Let $A$ be a Noetherian ring, $R$ be standard graded finitely generated $A$-algebra, $R_{+}$ be its irrelevant ideal, $M$ be a finitely generated $R$-module. Let $Q$ be a $M$-reduction of $R_+$, generated by linear form $x_{1},...,x_{s}$. For $i=1,...,s$, put $z_{i}=\sum_{j=1}^{s}u_{ij}x_{j}$ where $U=\lbrace u_{ij}|i,j=1,...,s\rbrace$ is a matrix of indeterminates. Put $A'=A[U,\text{det}(U)^{-1}], R'=R\otimes_{A}A', M'=M\otimes_{A}A'$ then $A'$ is a flat extension of $A$.

As I understand $A'$ is a flat extension of $A$ if regarded as $A$ module, tensoring a exact sequence with $A'$ will give us an exact sequence.My questions are

How can we prove that the ring $A'$ constructed above satisfies the above property ?
From a commutative ring $A$, how can we construct its flat extension ?

I also have questions in the proof of the proposition 2.1 in that paper

Let $S=A[X_{1},...,X_{S}, Y_{1},...,Y_{v}]$ be a polynomial ring over a commutative Noetherian ring $A$. This ring can be viewed as a bigraded ring if we associate the degree for $X_{i}$ and $Y_{j}$ as $\text{deg}(X_{i})=(1,0), i=1,...,s; \text{deg}(Y_{j})=(d_{j}, 1), j=1,...,v$

Now, let $\mathcal{M}$ be a finitely generated graded module over $A[X_{1},...,X_{s}, Y_{1},]$ . For a fixed number $n$, put $\mathcal{M}_{n}=\oplus_{a\ge0}\mathcal{M}_{(a,n)}$ . Then $\mathcal{M_n}$ is a finitely generated graded module over the naturally graded polynomial ring $A[X_1,...,X_s]$. If $s=0$ then $\text{reg}(\mathcal(M_{n})$ is the invariant : $a(\mathcal{M_{n}})=\text{max}\lbrace a|\mathcal{M_{(a,n)}}\neq 0\rbrace$

3-Question : Why $\text{reg}\mathcal{M_n})$ is equal to $a(\mathcal{M_n})$ ?

As I understand , in $\mathcal{M_{(a,n)}}$, the index $a$ is graded for the variables $X_i$ and the index $n$ is graded for the variables $Y_{J}$ and then $\mathcal{M_{n}}$ is graded module over $A[X_1,…,X_s]$ but it is not a graded module over $A[Y_1,…,Y_v]$. So if $s=0$, and $n$ is fixed then we get nothing on $\mathcal{M_n}$. So, what is the point here ?

Proposition 2.1 in that paper says that

Let $\mathcal{M_n}$ be a finitely generated bigraded module over the bigraded ring $A[Y_1,...,Y_v]$. Then $a(\mathcal{M_n})$ is asymptotically a linear function with slope $\leq d_v$

Here is the argument in the proof :

The case $v=0$ is trivial.Consider the exact sequence : $0\rightarrow [0_{\mathcal{M}}:Y_{v}]_{(a,n)}\rightarrow \mathcal{M}_{(a,n)}\xrightarrow{Y_{v}}\mathcal{M}_{(a+d_{v},n+1)}\rightarrow \mathcal{M/Y_{v}M}_{(a+d_{v},n+1)}\rightarrow 0$

Since $0_{\mathcal{M}}:Y_{v}$ and $\mathcal{M}/Y_{v}\mathcal{M}$ can be viewed as bigraded modules over $A[Y_1,...,Y_{v-1}]$, using induction we may assume that $a([0_{\mathcal{M}}:Y_{v}]_{n})$ and $a([\mathcal{M}/Y_{v}\mathcal{M}]_{n})$ are asymptotically linear functions with slope $\leq d_v$. As consequence : $$a([0_{\mathcal{M}}:Y_{v}]_{n})+d_v\ge a([0_{\mathcal{M}}:Y_{v}]_{n+1})$$ $$a([\mathcal{M}/Y_{v}\mathcal{M}]_{n})+d_v\ge a([\mathcal{M}/Y_{v}\mathcal{M}]_{n+1})$$ for large $n$.

My question for this part is :

4- How did the author use the induction ? If they use the induction on $v$ then why can they get the above two inequalities, since I think we can get the inequalities if we use induction on $n$.

Since $a(\mathcal{M}_{n})\ge a([0_{\mathcal{M}}:Y_{v}]_{n})$ for all $n$, we only need to consider the case that $a(\mathcal{M}_{m})> a([0_{\mathcal{M}}:Y_{v}]_{m})$ for infinitely many $m$. Putting this condition into the above exact sequence we get : $$a(\mathcal{M}_{m+1})=\text{max}\lbrace a(\mathcal{M}_{m})+d_{v},a([\mathcal{M}/Y_{v}\mathcal{M}]_{n+1})\rbrace $$

My question for this part is :

5-How can the author get the above information from the exact sequence ?

Here is my argument : We have : $Y_{v}\mathcal{M}_{n}=\oplus_{a\ge 0}Y_{v}\mathcal{M}_{(a,n)}:=\oplus_{a\ge 0}\mathcal{N}_{(a+d_{v},n+1)}$ . Then : $$a(Y_{v}\mathcal{M}_{n})=a(\oplus_{a\ge 0}\mathcal{N}_{(a+d_{v},n+1)})$$ $$=\text{max}\lbrace a+d_{v}|\mathcal{N}_{(a+d_{v},n+1)}\neq 0\rbrace$$ $$=\text{max}\lbrace a+d_{v}|Y_{v}\mathcal{M}_{(a,n)}\neq 0\rbrace$$ $$=d_{v}+\text{max}\lbrace a|\mathcal{M}_{(a,n)}\neq 0\rbrace$$ $$=d_{v}+a(\mathcal{M_{n}})$$ Since $Y_{v}\mathcal{M}_{n}\subseteq\mathcal{M}_{n+1}$ then $a(Y_{v}\mathcal{M}_{n})\le a(\mathcal{M}_{n+1})$ or $a(\mathcal{M}_{n+1})\ge d_{v}+a(\mathcal{M}_{n})$ .

6-Am I wrong anywhere ?

7-What is the aim of the authors in the rest of the proof ?

I know that my questions are very long and may be hard to follow. If you have any question on this or this kind of questions are not appropriate with MO please let me know.

Thank for reading!

Filter-regular sequence and regularity

2012-10-23T02:05:56Z

Let $A$ be a commutative Noetherian ring, $R$ be a standard graded algebra over $A$, $M$ be finitely generated graded $R$-module. Let $R_{+}$ be the irrelevant ideal. The Castelnuovo-Mumford regularity of $M$ or regularity for short is defined to be : $\text{reg}(M):=\text{max}\lbrace a(H_{R_+}^{i}(M))+i|i\ge 0\rbrace$. Let $x_1,...,x_s$ be linear form in $R$. This set of elements is called a $M$-filter regular sequence if $x_{i}\notin \mathfrak{p}$ for any associated prime $\mathfrak{p}\nsupseteq R_{+}$ of $(x_1,...,x_{i-1})M$ for $i=1,...,s$

Then, people claim that : $\text{reg}(M)=\text{max}\lbrace a((x_1,...,x_i)M:R_{+}/(x_1,...,x_{i})M)|i=1,...,s\rbrace$

Could you explain for me why is it ? What is the motivation of filter regular sequence ?

Question on bigraded modules

2012-10-15T03:16:27Z

Let $R$ be a polynomial ring $k[x_1,...,x_n]$, let $f_1,...f_s$ be some non-zero polynomial sin $R$ of degree $p_1,...,p_s$ respectively.Define $S$ by $k[X_1,...,X_n, T_1,...T_s]$ with bigrading defined by $degX_i=(1,0)$ and $degT_j=(p_j,1)$. For a bigraded $S$-module $M=\bigoplus_{p,n\in\Bbb{N}}M_{(p,n)}$, define $M^{(n)}$ to be the graded $R$-module $\bigoplus_{p\in\Bbb{N}}M_{(p,n)}$ in which the action of $x_i$ can be understanded as $X_i$ with its obvious grading.

There are two claims that I could not prove, so I decided to post it here, and I hope you will help me to prove it.

1-The functor $(.)^{(n)}$ is an exact functor.

2-There are the isomorphisms: $S(-a,-b)^{(n)}\cong S^{(n-b)}(-a)\cong \bigoplus_{a_1+...+a_s=n-b}R{(-a_1p_1-...-a_sp_s-a)}$

Thank for reading my question!

On the generator of power of ideal

2012-10-09T01:07:29Z

Let $I$ be a graded ideal in a polynomial ring $R$, which is generated minimally by $x_1,...,x_k$. Then the power of $I$, i.e $I^t$ is generated by monomials of the form $x_{1}^{a_1}...x_{n}^{a_{n}}$ where $a_1+...+a_n=t$. Denote this set by $S$.

Can we say anything (others than above)about the minimal generating set of $I^{t}$? Is it $S$ ?

Given a minimal generating set for a graded ideal in a graded commutative ring, from these how much do we know about the minimal generating set for the power of it?

Edit : Here is an example for precising my question :

In the polynomial ring $k[x,y,z]$ let $I=(x^2, xy^3, y^2z^3)$, then $I^2=(x^4, x^2y^6, y^4z^6, x^3y^3, xy^5z^3, x^2y^2z^3)$

Is $\lbrace x^4, x^2y^6, y^4z^6, x^3y^3, xy^5z^3, x^2y^2z^3\rbrace$ a minimal generating set for $I^2$ ?

Update There are some typing mistake that I have not noticed. I have change my question. This time, the generating set of $I$ is minimal. So what can we say about the generating set for $I^2$ above ? Is it minimal? Thank you everyone for helping me answer my question!

Castelnuovo-Mumford regularity and degree of generator.

2012-10-08T12:30:46Z

Let $R$ be a polynomial ring over a field $k$,: $k[x_{1},..x_{n}]$, $\mathfrak{m}=(x_0,...,x_{n})$ and $M$ be a finitely generated $R$ module.

In a paper of Kodiyahlam, he define the Castelnuovo-Mumford regularity of $M$ to be the least integer number $m$ such that for every $j$ the $j$-th syzygy of $M$ is generated in degree less or equal $m+j$.Then, he conclude that the Castelnuovo-Mumford regularity of $M/\mathfrak{m}M$ is equal to the maximal degree of generator of $M$.

Could you please so me why the CM regularity of $M/\mathfrak{m}M$ is equal to the maximal degree of generator of $M$ ?

If $I$ and $J$ are two finitely generated ideal of $R$ and $J\subseteq I$ then do we have the CM regularity of $J$ is less or equal the CM regularity of $I$ ?

Comment by Knot

2013-03-28T13:21:14Z

@ Noah Stein. "the" upper bound is O(1), O(log n), O(\sqrt(n)) or O(n)... We do not need the exact value of F(n).

Comment by Knot

2013-03-28T13:17:47Z

And thank for your useful suggestion, Nadeau. :)

Comment by Knot

2013-03-28T13:05:06Z

I'm sorry, this is a typo. Yeah, it is 2^n at the denominator

Comment by Knot

2013-02-17T09:39:25Z

It seems to me that $\frac{\sum a_{ij}}{2^n}=O(\log n)$. Is it correct?

Comment by Knot

2012-11-05T04:17:46Z

@Graham Leuschke : Thanks !

Comment by Knot

2012-11-05T04:17:29Z

@William Sawin : Thanks. I really appreciate that. What about the other questions ?

Comment by Knot

2012-10-16T01:50:07Z

@Ralph: Thank you very much for answering my question. May I ask : Why in $(*)$ the component containging the variables $T1,...T_s$ disappear?

Comment by Knot

2012-10-15T13:58:10Z

@Ralph: You are right. In fact, I proved it but I am not sure about it, the graded structure confuses me.

Comment by Knot

2012-10-15T13:43:41Z

@Neil Epstein : What will happen if I is a monomial ideal ?

Comment by Knot

2012-10-15T13:40:56Z

@Ralph: Thank you, I have confused with $R$ and $S$. The 2nd question is in fact a results of a lemma in a paper, that I do not think it is trivial but I have not proved it yet, so I decided to post it here. Thank you very much! P.s : The functor is from the category of bigraded modules to the category of bigraded module, I think.

Comment by Knot

2012-10-15T03:56:24Z

@Mariano Suarez-Alvarez : Thank you very much! I edited it.

Comment by Knot

2012-10-13T15:24:14Z

Dear Hailong Dao, firstly I want to say thank for your answer, it helps me alot. Secondly, I do not care about the fact that the question may let people think I am stupid, I just want to know the answer and how to think about it, it is more worthy for me. About your answer, can I ask(may be another stupid one) a question : If $x_1,..x_n$ minimally generate a graded ideal $I$, and they form a regular sequence, then S is the minimal generating set ?

Comment by Knot

2012-10-11T23:34:31Z

Sorry everybody for my stupid mistake in the example. I have edited it. Please help me. Thanks.

Comment by Knot

2012-10-11T17:18:20Z

@Mahdi: I just want to apply the algorithm in a very special case : Computing the reduction that I need right now, and I do not have much time to think about the other things :(. Btw, thank you very much!

Comment by Knot

2012-10-11T16:27:29Z

@Dima Pasechnik : Could you please tell me which book that I can read for applying Grobner basis to compute the reduction ?