Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

First, we define a sequence $t_{1},t_{2},\cdots,t_{k}$ of n-tuples dicksonian, if $\forall 1\leq i < j\leq k,$ there does not exist a non-negative n-tuple t such that $t_{i}+t=t_{j}.$ For example, any lexicographically decreasing sequnence is dicksonian. By Dickson's lemma, every dicksonian sequence is finite. Let $(a_{1}^{1},\cdots,a_{n}^{1}),(a_{1}^{2},\cdots,a_{n}^{2}),\cdots,(a_{1}^{k},\cdots,a_{n}^{k})$ be a dicksonian sequence of n-tuples of non-negative integers such that $\sum_{i=1}^{n}(a_{i}^{j})=f(j)$ for all $j,1\leq j\leq k,$ where $f: \mathbb{Z} _{\geq0} \rightarrow \mathbb{Z} _{\geq0}$ is a fixed function.

Note that in the paper, "G. Moreno Socias, An Ackermannian polynomial ideal" it actually considered the maximal length of a dicksonian sequence such that $f(1)=d,f(i+1)=f(i)+1,\forall i\geq 1$, and this result is represented as a Ackermann function. Considering the characteristic of the dicksonian sequence satisfying the requirement with the maximal length with $n=3,d=3,$ given at the end of this paper, I want to ask the following question:

What is the possible maximal length for a dickson sequence such that $f(1)=d,f(i+1)=f(i)+1,\forall i\geq 1$, and the sum of the first two entries of every n-tuple in this dicksonian sequence is a fixed number, say m.?

Note that the position of the two entries with a fixed sum in a n-tuple may further affect the final result, I may further ask the following question:

What is the possible maximal length for a dickson sequence such that $f(1)=d,f(i+1)=f(i)+1,\forall i\geq 1$, and the sum of the two entries at position $i_0,j_0, 1\leq i_0\lt j_0\leq n$ of every n-tuple in this dicksonian sequence is a fixed number, say m.?

share|improve this question
    
Why is the Tex not completely displayed? –  Jiang May 6 '11 at 5:18
    
Also, isn't $1 \leq i{\geq 0}$ a bit redundant? –  Ricky Demer May 6 '11 at 5:40
    
I don't understand the question. Is the Socias paper available somewhere? –  Gerry Myerson May 6 '11 at 6:28
    
@Ricky Demer, I have finally made the Tex displayed completely. –  Jiang May 6 '11 at 9:42
    
@Gerry Myerson, the paper can be found here:springerlink.com/content/y36195n14590l4l3. Note that the author first reduced his question to considering only monomial polynomial ideals, then the total degree of $p_d,p_{d+1},\cdots,$ increased by 1 each step. –  Jiang May 6 '11 at 9:48
add comment

1 Answer 1

I lack the rep to comment. This paper may help with the calculations.

Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma http://arxiv.org/abs/1007.2989

share|improve this answer
    
Thanks Vijay, I have not met this paper before. –  Jiang May 6 '11 at 9:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.