Thanks for the improvement! Here's a general upper bound for the case 1 < n/m < = 3/2: I'm going to use my normalization -- your fractions are driving me crazy! Recall that we seek arrays with m rows, n columns, such that all row sums equal n and all column sums equal m. We want an upper bound on U(m, n), the smallest non-zero entry. Let p be the average number of non-zeroes per row, q the average number of non-zeroes per column. Since m < n, we have q < p. First suppose that there is a column with only one non-zero; its value will be m. Look in the same row (of that non-zero) and there must be some other non-zeroes, since the row sum n is greater than m. An upper bound on this other non-zero is U(m, n) <= n - m <= n - 2/3n = n/3. Now suppose none of the columns have a single non-zero. Then q >= 2, and so p > 2. That tells us that some row has at least three non-zeroes from which we get the bound U(m, n) <= n/3. Five entries in my table actually achieve this bound. Veit On Jan 12, 2009, at 11:25 PM, Michael Reid wrote:
several more values, to cover your table:
T(7, 8) = 5/112 ; 4 * 5/112 + 2 * 3/56 + 4 * 1/16 + 2 * 1/14 + 4 * 9/112 T(7, 9) = 5/125 ; 6 * 5/126 + 3 * 1/21 + 3 * 4/63 + 6 * 1/14 T(8, 9) = 1/24 ; 6 * 1/24 + 6 * 1/18 + 6 * 5/72
the latter two agree with your table; but the first gives an improvement. (no contradiction, since you only gave a lower bound.)
mike
Here are my lower bounds for U(m, n):
1 2 3 4 5 6 7 8 9 1 1 2 1 2 3 1 1 3 4 1 2 1 4 5 1 1 5/4 3/2 5 6 1 2 3 2 2 6 7 1 1 5/4 5/3 5/3 2 7 8 1 2 4/3 4 2 2 9/4 8 9 1 1 3 7/4 2 3 5/2 3 9
The entry in column 4 row 7 is the bound on U(4, 7), which in fact equals the optimum value that was the subject of previous posts ( U(m, n) = m n T (m, n) ). I suspect several of my bounds are optimal values. I'm happy to supply the partitions to anyone interested.
i've also "calculated" some values. recall that my T(m, n) is the maximum c such that there exists a partition of 1 with each part
= c , and which is a simultaneous refinement of 1/m + 1/m + ... + 1/m = 1 and of 1/n + 1/n + ... = 1/n = 1 .
i believe i have a valid proof for each of the values below. i also give one such partition for each; showing that it's a refinement is easy.
T(m, n) = 1/n if m divides n ; n * 1/n
T(2, 2n+1) = 1/(2(2n+1)) ; (4n+2) * 1/(2(2n+1))
T(3, 4) = 1/12 ; 12 * 1/12 T(3, 5) = 1/12 ; 4 * 1/12 + 2 * 1/10 + 4 * 7/60 T(3, 7) = 5/84 ; 4 * 5/84 + 6 * 1/14 + 4 * 1/12 T(3, 8) = 1/18 ; 6 * 1/18 + 6 * 5/72 + 2 * 1/8 T(3, 10) = 2/45 ; 6 * 2/45 + 6 * 1/18 + 2 * 1/10 T(3, 11) = 1/24 ; 8 * 1/24 + 2 * 1/22 + 8 * 13/264 + 2 * 1/11 T(3, 13) = 11/312 ; 8 * 11/312 + 2 * 1/26 + 8 * 1/24 + 4 * 1/13
T(4, 5) = 3/40 ; 4 * 3/40 + 2 * 1/10 + 4 * 1/8 T(4, 6) = 1/12 ; 12 * 1/12 T(4, 7) = 5/84 ; 6 * 5/84 + 2 * 1/14 + 6 * 1/12 T(4, 9) = 7/144 ; 8 * 7/144 + 2 * 1/18 + 8 * 1/16 T(4, 10) = 1/20 ; 20 * 1/20 T(4, 11) = 9/220 ; 10 * 9/220 + 2 * 1/22 + 10 * 1/20 T(4, 4n+2) = 1/(2(4n+2)) ; (8n+4) * 1/(2(4n+2))
T(5, 6) = 1/15 ; 6 * 1/15 + 6 * 1/10 T(5, 7) = 1/21 ; 3 * 1/21 + 6 * 1/15 + 6 * 8/105 T(5, 8) = 1/20 ; 4 * 1/20 + 4 * 3/40 + 4 * 1/8 T(5, 9) = 2/45 ; 6 * 2/45 + 6 * 1/15 + 3 * 1/9
T(6, 7) = 1/21 ; 12 * 1/21 + 6 * 1/14 T(6, 8) = 1/24 ; 24 * 1/24 T(6, 9) = 1/18 ; 18 * 1/18
these appear to agree with your lower bounds on the overlap.
mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun