[math-fun] A problem on highly-cancelling polynomials
Let m be a "whoo-whee number" if there exist 4 polynomials A(x), B(x), C(x), D(x) with degree(A)=degree(B)=m, degree(C)=degree(D)=m+1, all coefficients in all polynomials +-1, and A(x)A(1/x)+B(x)B(1/x)+C(x)C(1/x)+D(x)D(1/x) = 4m+6. Note the right hand side does not depend on x, so we are asking for a lot of cancellation here. I can show there are an infinite set of whoo-whee numbers. Computers seem to think every number is a whoo-whee number (at least as far out as computers can see). THE (UNSOLVED) PROBLEM: prove the count of whoo-whee numbers below X ultimately grows at least like some positive power of X, for example X^0.001. Ideas welcome even if not solutions. This is an example of a frustrating combinatorial construction problem where the gulf between what seems true (all numbers) and what I can prove (a very sparse set of numbers) is enormous, but it might not be hard to break the impasse. Warren D. Smith warren.wds AT gmail.com
Consider the corners of the (say) unit n-cube: {0,1}^n, in R^n. QUESTION: What is the size |X(n)| of a largest subset X(n) of the 2^n corners, such that all nonzero distances in X(n) have the same value? The distinct distances are {sqrt(k) | 0 <= k <= n}. For a fixed k > 0, the number of distances = sqrt(k) is 2^(n-1) * C(n,k), where C(n,k) := n!/(k! (n-k)!). MORE GENERAL QUESTION: What is the size |X(n,k)| of a largest subset X(k,n) having all its nonzero distances = sqrt(k) ? (These questions can be rephrased to ask what is the size of the largest clique in the constant-distance graphs for {0,1}^n.) F'rinstance, in {0,1}^4, the graph of all distances = sqrt(2) has two components. Each is isomorphic to what you get if you connect all pairs of vertices of an octagon (or 3-cube), except antipodes, with an edge. So each component of the graph has 8 vertices and 24 edges. The largest clique has only 4 vertices. --Dan
The largest subset that forms a simplex cannot be larger than n+1, and by the Hadamard conjecture these exist for all n=3 mod 4. Here's the construction: Take a Hadamard matrix of order n+1 and flip the sign of each row so that the first element equals 1. Delete the first element in each row and replace -1 with 0. The n+1 rows are then your elements X(n). The Hamming distance between any pair of elements is (n+1)/2; this is the square of the euclidean distance. -Veit On Oct 6, 2012, at 6:30 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Consider the corners of the (say) unit n-cube: {0,1}^n, in R^n.
QUESTION: What is the size |X(n)| of a largest subset X(n) of the 2^n corners, such that all nonzero distances in X(n) have the same value?
The distinct distances are {sqrt(k) | 0 <= k <= n}.
For a fixed k > 0, the number of distances = sqrt(k) is 2^(n-1) * C(n,k), where C(n,k) := n!/(k! (n-k)!).
MORE GENERAL QUESTION: What is the size |X(n,k)| of a largest subset X(k,n) having all its nonzero distances = sqrt(k) ?
(These questions can be rephrased to ask what is the size of the largest clique in the constant-distance graphs for {0,1}^n.)
F'rinstance, in {0,1}^4, the graph of all distances = sqrt(2) has two components. Each is isomorphic to what you get if you connect all pairs of vertices of an octagon (or 3-cube), except antipodes, with an edge. So each component of the graph has 8 vertices and 24 edges. The largest clique has only 4 vertices.
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Right. (Warren also mentioned this in e-mail to me.) I don't know how likely it is that the Hadamard conjecture is true, however. --Dan On 2012-10-07, at 9:04 AM, Veit Elser wrote:
The largest subset that forms a simplex cannot be larger than n+1, and by the Hadamard conjecture these exist for all n=3 mod 4. Here's the construction:
Take a Hadamard matrix of order n+1 and flip the sign of each row so that the first element equals 1. Delete the first element in each row and replace -1 with 0. The n+1 rows are then your elements X(n). The Hamming distance between any pair of elements is (n+1)/2; this is the square of the euclidean distance.
-Veit
On Oct 6, 2012, at 6:30 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Consider the corners of the (say) unit n-cube: {0,1}^n, in R^n.
QUESTION: What is the size |X(n)| of a largest subset X(n) of the 2^n corners, such that all nonzero distances in X(n) have the same value?
The distinct distances are {sqrt(k) | 0 <= k <= n}.
For a fixed k > 0, the number of distances = sqrt(k) is 2^(n-1) * C(n,k), where C(n,k) := n!/(k! (n-k)!).
MORE GENERAL QUESTION: What is the size |X(n,k)| of a largest subset X(k,n) having all its nonzero distances = sqrt(k) ?
(These questions can be rephrased to ask what is the size of the largest clique in the constant-distance graphs for {0,1}^n.)
F'rinstance, in {0,1}^4, the graph of all distances = sqrt(2) has two components. Each is isomorphic to what you get if you connect all pairs of vertices of an octagon (or 3-cube), except antipodes, with an edge. So each component of the graph has 8 vertices and 24 edges. The largest clique has only 4 vertices.
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The evidence that the Hadamard conjecture is true is overwhelming - look at how fast the number of H matrices or order n grows: see A007299 in the OEIS - and also there are a huge number of constructions. On Sun, Oct 7, 2012 at 12:31 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Right. (Warren also mentioned this in e-mail to me.)
I don't know how likely it is that the Hadamard conjecture is true, however.
--Dan
On 2012-10-07, at 9:04 AM, Veit Elser wrote:
The largest subset that forms a simplex cannot be larger than n+1, and by the Hadamard conjecture these exist for all n=3 mod 4. Here's the construction:
Take a Hadamard matrix of order n+1 and flip the sign of each row so that the first element equals 1. Delete the first element in each row and replace -1 with 0. The n+1 rows are then your elements X(n). The Hamming distance between any pair of elements is (n+1)/2; this is the square of the euclidean distance.
-Veit
On Oct 6, 2012, at 6:30 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Consider the corners of the (say) unit n-cube: {0,1}^n, in R^n.
QUESTION: What is the size |X(n)| of a largest subset X(n) of the 2^n corners, such that all nonzero distances in X(n) have the same value?
The distinct distances are {sqrt(k) | 0 <= k <= n}.
For a fixed k > 0, the number of distances = sqrt(k) is 2^(n-1) * C(n,k), where C(n,k) := n!/(k! (n-k)!).
MORE GENERAL QUESTION: What is the size |X(n,k)| of a largest subset X(k,n) having all its nonzero distances = sqrt(k) ?
(These questions can be rephrased to ask what is the size of the largest clique in the constant-distance graphs for {0,1}^n.)
F'rinstance, in {0,1}^4, the graph of all distances = sqrt(2) has two components. Each is isomorphic to what you get if you connect all pairs of vertices of an octagon (or 3-cube), except antipodes, with an edge. So each component of the graph has 8 vertices and 24 edges. The largest clique has only 4 vertices.
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
Hmm, I wonder if it could be true just from favorable probability -- but undecidable. (As the Twin Prime Conjecture may be.) --Dan On 2012-10-07, at 11:50 AM, Neil Sloane wrote:
The evidence that the Hadamard conjecture is true is overwhelming - look at how fast the number of H matrices or order n grows: see A007299 in the OEIS - and also there are a huge number of constructions.
participants (4)
-
Dan Asimov -
Neil Sloane -
Veit Elser -
Warren Smith