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

Suppose I have a bunch of nonnegative integers $(a_{ijkl})_{1 \leq i \leq j \leq k \leq l \leq 17}$ such that for all 17-tuples nonnegative integers $w_t$ (for $1 \leq t \leq 17$) we have that $$\min_{1\leq i\leq j\leq k \leq l\leq 17}(a_{ijkl} + w_i + w_j + w_k+w_l) \leq \frac{4}{17}\sum_{1 \leq t \leq 17} w_t.$$ What can we say about the $a_{ijkl}$? Are they bounded? What are the optimal bounds? I would like to get as much information on the $a_{ijkl}$ as possible. This problem comes from a question in number theory I'm trying to answer, but as you can see, this has a smell of linear programming, of which I know nothing at all. Also, maybe some things can be done with a computer, but I'm not good with computers...

(EDIT) If you suppose moreover that for all $t$, at least one of the inequalities $a_{ijkl} \geq n$, where $n$ is the number of indices from $(i,j,k,l)$ which are equal to $t$ ($n \geq 1$), is false, can we get something more?

(MOTIVATION) This comes from a semistability condition in geometric invariant theory.

share|improve this question
2  
Do you mean to have $i \leq j \leq k \leq l$ in the first line? –  S123 Sep 6 '11 at 16:24
1  
Here is a first idea: Note that $\frac{4}{17}21<4<\frac{4}{17}22$. So if the $w_t$ sum to at most 21, the left side is an integer, the right side is less than 5, hence the $a_{ijkl}$ at which the minimum is obtained is $0$. In particular, consider $w_1=w_2=w_3=w_4=2$ and $w_t=1$ for $5\leq t\leq 17$. Now if one of $i,j,k,l$ equals 1,2,3,4, then $a_{ijkl}+w_i+w_j+w_k+w_l\geq a_{ijkl}+5>\frac{4}{17}\cdot21$. So one of the $a_{ijkl}$ with all of $i,j,k,l\geq 5$ has to be zero. By changing which $w_t$ are 2 and which are 1, we can see that there must be a "many" zeroes among the $a_{ijkl}$. –  Max Horn Sep 6 '11 at 16:36
    
@SPG: yes. @Max: nice idea! Notice also that we can really take $i = j = k = l$ in the inequality. –  Wanderer Sep 6 '11 at 17:24
1  
You should not have responded so quickly to SPG's question! $i≤j≤k≤l$ is not consistent with $1≤i,j,k,l≤17$. –  TonyK Sep 6 '11 at 18:03
2  
Notice that the character of the inequality is preserved if the w's are multiplied by an integer or have the same integer added to them. So for testing purposes you can assume that some w are zero and many others are 1. I think you will be able to show that at least 5 of the 21 choose 4 a's are 0, and maybe even 17, but not much else. In particular I see no upper bound on even the second smallest of the a's. Gerhard "Ask Me About System Design" Paseman, 2011.09.06 –  Gerhard Paseman Sep 6 '11 at 18:52
show 5 more comments

2 Answers

Take $a_{iiii}=0$ for all $i=1,\dots,17$ and let the other $a$'s be arbitrary large. Then the inequality is satisfied.

Indeed, let $w_1, \dots, w_{17}$ be arbitrary nonnegative integers. Without loss of generality assume that $$\min \{ w_1, \dots, w_{17} \} = w_1.$$ Then $$\min_{1\leq i\leq j\leq k\leq l\leq 17} (a_{ijkl} + w_i + w_j + w_k + w_l) \leq a_{1111} + 4w_1 = 4w_1 \leq \frac{4}{17} \sum_{t=1}^{17} w_t$$ as required.

Hence, $a_{ijkl}$ are not bounded in general.

share|improve this answer
add comment

I see this as more of a set selection problem or a combinatorial design problem than a number theory problem, unless there is something else about the $a_{ijkl}$ that is not being mentioned.

By setting 4 of the w's to 1 and the rest to 0, I can convince myself that 5 of the a's are zero. Conversely, choose the a's anyway you like, but let me set 5 of them to zero: $a_{1111}$, and four others which partition the index set. Then for any tuple of w's, either one of the four other a's I picked selects a below average subtuple of w's to sum, or they are all above average and $w_1$ is less than 1/17th of the sum. Your inequality will be satisfied by this selection of a's and any w's, and it will not tell me a thing about the a's you picked.

Gerhard "Ask Me About System Design" Paseman, 2011.09.06

share|improve this answer
    
Of course, you can use this to characterize the tuples of a's which satisfy the given property, but it still seems pretty weak. You might see if there is some other condition satisfied by the a's that would make finding the a's more revealing. Gerhard "Ask Me About System Design" Paseman, 2011.09.06 –  Gerhard Paseman Sep 6 '11 at 19:34
    
Given the above answer is acceptable, one thing I would like even more than having it accepted is learning of the problem that gave rise to this question. Would you tell us about it? Gerhard "Ask Me About System Design" Paseman, 2011.09.06 –  Gerhard Paseman Sep 6 '11 at 19:42
    
I added a brief comment about the origin of the question and also some other condition satisfies by the $a$'s. –  Wanderer Sep 6 '11 at 20:31
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.