Wikipedia:Reference desk/Archives/Mathematics/2016 June 7

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 7

Algorithm to enumerate (n^2+n) sets of size n from n^2 items

I am seeking an algorithm to enumerate (n^2+n) sets of size n from n^2 items where every pair of items are in common in one and only one set.

Firstly, I believe it is possible. Secondly I have an algorithm that works for prime n: Arrange the items in a square. Read the columns for the "+n" sets. Then (for the n^2 sets) form n bunches of n sets, each bunch starting with an item from the left hand column and taking one item from each subsequent column using a different "drop per column" for each bunch. I'm using 'bunch' as a non-mathsy word instead of the more natural word "group" which might have math meaning.

Example

a b c
d e f
g h i

Columns adg, beh, cfi;
Drop 0 bunch abc, def, ghi;
Drop 1 bunch aei, dhc, gbf;
Drop 2 bunch ahf, dbi, gec.

This algorithm fails when n is non-prime. I can manually enumerate 20 sets for n=4, but can't extend the method to 6, 8 or 9 yet.

Any suggestions please? -- SGBailey (talk) 06:14, 7 June 2016 (UTC)

Would that be the Steiner system $S(2,n,n^{2})$? I think this may be slightly useful to get started. 5.11 seems to imply that the sets you wish to generate might not be possible for non-prime power n. —  crh ₂₃  (Talk) 14:10, 7 June 2016 (UTC)

As you say, it looks as though Steiner is what I want. I (believe I) can do S(2, prime, prime^2) and S(2,4,16). My first stumbling block would be S(2,6,36). Your refs need careful reading. Whether 5.11 says it is impossible I need to study. Thanks - this will keep me going for a week or too. -- SGBailey (talk) 16:27, 7 June 2016 (UTC)

You might try [1], section 4 in particular. It mentions the Thirty-six officers problem in regard to S(2,6,36). --RDBury (talk) 08:18, 8 June 2016 (UTC)

Elegant Solution to Sharp Inequality

How could we prove, without the aid of a calculator, that ${\sqrt[{5}]{12}}-{\sqrt[{12}]{5}}>{\dfrac {1}{2}}$ ? Moving the negative term to the right hand side, and then exponentiating, is —for painfully obvious reasons— unfeasible. Perhaps some clever manipulation might show the way out of this impasse, but I fail to see how... — 82.137.54.252 (talk) 07:51, 7 June 2016 (UTC)

Why do you think there is an easy way? ${\sqrt[{5}]{12}}-{\sqrt[{12}]{5}}\approx 1.64375-1.14353=0.50022$ That is so close to 0.5 that it doesn't leave much room for approximations, and you seem to reject both calculating the root or expanding a long exponential, so I don't see where you have any path forward. Dragons flight (talk) 08:10, 7 June 2016 (UTC)

Given my username and the section title, I feel somewhat obligated to attempt to reply to this, but I don't see a way either. The difference is so close to 0.5 that any approximations that would be simple enough to use without a calculator would not be accurate enough to prove the inequality. Double sharp (talk) 09:01, 7 June 2016 (UTC)

(Huh. So the word "inequation" is apparently a thing. I confess that I do not remember having heard it.) Double sharp (talk) 13:38, 7 June 2016 (UTC)

Hm. inequation says that it is a statement of inequality (which is a relation). But equation says that one of those is an equality. This is a troublesome state of affairs... SemanticMantis (talk) 14:27, 7 June 2016 (UTC)

I've tweaked the opening sentence of equation accordingly. Loraof (talk) 15:17, 7 June 2016 (UTC)

The usual term for these sorts of sentences is "inequality", not "inequation". I smell the odor of MathWorld here, which is one of the two references at inequation, the other being a book called "The A to Z of Mathematics" or some such, another name that does not inspire high confidence (sounds like a tertiary ref).

Wikipedia should not be used for these sorts of language-reform efforts. My opinion is that we should rework the articles to refer to the sentences primarily as "inequalities", while mentioning somewhere that the term "inequation" also exists. --Trovatore (talk) 16:01, 7 June 2016 (UTC)

I have a hazy recollection from long ago, an undergrad math professor using these words a bit differently to distinguish assertions from assignations, different from the notion in our articles of distinguishing statements from relations. E.g. 4=2+2 is an assertion (and a statement of equality) but 4=x is more like an assignment; it is an equation by fiat only. Does that ring a bell with anyone else? My first thought when seeing 'inequation' was that maybe somebody was taking this distinction to inequality as well, e.g. maybe 4>2 is considered an inequation while 4>x is considered an inequality. I cannot support this idea with any references at present though, so maybe my hazy recollections are playing tricks on me :) Finally, I'll add that cursory googling seems to indicate that 'inequation' has more use in BrEng (e.g. BBC [2]), so there may be an WP:ENGVAR issue conflated with a semantic one. SemanticMantis (talk) 18:29, 7 June 2016 (UTC)

I think you need to look up assignation :-) I doubt that's the issue. 4=x is a fine equation in general, albeit one containing a free variable. Assignments are generally distinguished by context (for example, "let x=4"), and there's no obvious corresponding concept in inequalities (you can say "assume x<4", but that's an assumption, which is different from an assignment, though you might be able to dispense with assignments by replacing them with assumptions). However the ENGVAR thing is a possibility; I would be interested to hear more evidence on that. --Trovatore (talk) 18:40, 7 June 2016 (UTC)

It came out as slip of the tongue, but then I did look it up, and decided it was fine, as the second definition in my OSX copy of NOAD is pretty much what we mean when we talk about assignments for variables, and this is also supported by sense 2 of your your wiktionary link. In case you're curious, I haveAssignation: "the allocation or attribution of someone or something as belonging to something." Pretty much a synonym to the second sense of Assignment: "the attribution of someone or something as belonging." So maybe you could benefit by looking in to Muphry's_law ;)

Anyway, I do know how to talk about free variables and assumptions and assignments, I just thought I'd share a thought I had about a possible distinction. SemanticMantis (talk) 19:01, 7 June 2016 (UTC)

• Does this work?

It can be shown by multiplication and division that 263/160 is an underestimate of ${\sqrt[{5}]{12}}$

It can be shown by multiplication and division that 183/160 is an overestimate of ${\sqrt[{12}]{5}}$

$263/160-183/160=80/160=0.5$ exactly.

Hence, (${\sqrt[{5}]{12}}-a)-({\sqrt[{12}]{5}}+b)=0.5$; where both a and b are positive.

${\sqrt[{5}]{12}}-a-{\sqrt[{12}]{5}}-b=0.5$

${\sqrt[{5}]{12}}-{\sqrt[{12}]{5}}=0.5+a+b$; where both a and b are positive.

${\sqrt[{5}]{12}}-{\sqrt[{12}]{5}}>0.5$.

--NorwegianBlue ^talk 21:38, 8 June 2016 (UTC)

I found two fractions with smaller numerators and denominators for which the same logic holds: 166/101 and 143/87. --NorwegianBlue ^talk 19:41, 9 June 2016 (UTC)

Maybe you meant to subtract 1/2 from the smaller of your two fractions? (Your first example has the smallest max denominator for any pair of rational numbers differing by at least 1/2 in the relevant interval.) --JBL (talk) 20:23, 9 June 2016 (UTC)

My point was that 166/101 and 143/87 both are underestimates of ${\sqrt[{5}]{12}}$

$166/101-1/2$ and $143/87-1/2$ are both overestimates of ${\sqrt[{12}]{5}}$

Since the numerator of 143/87 is odd, we will need to double the denominator when subtracting 1/2, i.e. 199/174.

If there is anything wrong with my attempt at showing the feasibility of proving Sharp's inequality by manual (albeit tedious) calculation, please let me know! --NorwegianBlue ^talk 07:51, 10 June 2016 (UTC)

No, nothing wrong, I didn't understand that you meant one number to stand for a pair. (Of course both your examples produce one fraction with denominator larger than 160.) --JBL (talk) 19:53, 10 June 2016 (UTC)

It is done in integer arithmetic like this. The number $z={\sqrt[{12}]{5}}-{\sqrt[{5}]{12}}$ satisfies a polynomial equation with integer coefficients, which are determined by eliminating x and y from the equations

$z=y-x$

$y^{12}=5$

$x^{5}=12$.

The elimination goes like this. First eliminate $y$ by substituting $y=x+z$ into $y^{12}=5$

$(x+z)^{12}=5$.

Expanding the binomial

$\sum _{i=0}^{12}{\binom {12}{i}}x^{i}z^{12-i}=5$.

Split the sum and substitute $x^{5}=12$.

$\sum _{i=0}^{4}{\binom {12}{i}}x^{i}z^{12-i}+\sum _{i=5}^{9}{\binom {12}{i}}12x^{i-5}z^{12-i}+\sum _{i=10}^{12}{\binom {12}{i}}12^{2}x^{i-10}z^{12-i}=5$.

Change indexes

$\sum _{i=0}^{4}{\binom {12}{i}}x^{i}z^{12-i}+\sum _{i=0}^{4}{\binom {12}{i+5}}12x^{i}z^{12-5-i}+\sum _{i=0}^{2}{\binom {12}{i+10}}12^{2}x^{i}z^{12-10-i}=5$.

obtaining the degree 4 equation

$\sum _{i=0}^{4}A_{i}x^{i}=0$

where

$A_{0}={\binom {12}{0}}z^{12}+{\binom {12}{5}}12z^{7}+{\binom {12}{10}}12^{2}z^{2}-5$

$A_{1}={\binom {12}{1}}z^{11}+{\binom {12}{6}}12z^{6}+{\binom {12}{11}}12^{2}z$

$A_{2}={\binom {12}{2}}z^{10}+{\binom {12}{7}}12z^{5}+{\binom {12}{12}}12^{2}$

$A_{3}={\binom {12}{3}}z^{9}+{\binom {12}{8}}12z^{4}$

$A_{4}={\binom {12}{4}}z^{8}+{\binom {12}{9}}12z^{3}$

A second equation of degree 4 is obtained by multiplying by $x$

$\sum _{i=0}^{4}A_{i}x^{i+1}=0$

and using $x^{5}=12$

$\sum _{i=0}^{3}A_{i}x^{i+1}+12A_{4}=0$.

So now $x^{5}$ is eliminated! The next step is to eliminate $x^{4}$

$\sum _{i=0}^{3}B_{i}x^{i}=0$

$\sum _{i=0}^{3}C_{i}x^{i}=0$

where

$B_{0}=A_{0}A_{3}-12A_{4}^{2}$

$B_{1}=A_{1}A_{3}-A_{0}A_{4}$

$B_{2}=A_{2}A_{3}-A_{1}A_{4}$

$B_{3}=A_{3}^{2}-A_{2}A_{4}$.

and

$C_{0}=B_{3}A_{0}$

$C_{1}=B_{3}A_{1}-A_{4}B_{0}$

$C_{2}=B_{3}A_{2}-A_{4}B_{1}$

$C_{3}=B_{3}A_{3}-A_{4}B_{2}$

Then eliminate $x^{3}$ :

$\sum _{i=0}^{2}D_{i}x^{i}=0$

$\sum _{i=0}^{2}E_{i}x^{i}=0$

where

$D_{0}=B_{0}C_{3}-B_{3}C_{0}$

$D_{1}=B_{1}C_{3}-B_{3}C_{1}$

$D_{2}=B_{2}C_{3}-B_{3}C_{2}$

and

$E_{0}=-C_{0}D_{2}$

$E_{1}=C_{3}D_{0}-C_{1}D_{2}$

$E_{2}=C_{3}D_{1}-C_{2}D_{2}$

Then eliminate $x^{2}$ :

$\sum _{i=0}^{1}F_{i}x^{i}=0$

$\sum _{i=0}^{1}G_{i}x^{i}=0$

where

$F_{0}=D_{0}E_{2}-D_{2}E_{0}$

$F_{1}=D_{1}E_{2}-D_{2}E_{1}$

and

$G_{0}=-E_{0}F_{1}$

$G_{1}=E_{2}F_{0}-E_{1}F_{1}$

Finally eliminate $x$ :

$F_{0}G_{1}-F_{1}G_{0}=0$

This polynomial equation in $z$ has the root $z={\sqrt[{12}]{5}}-{\sqrt[{5}]{12}}$ Bo Jacoby (talk) 14:18, 10 June 2016 (UTC).

Thank you, Bo Jacoby, that's fascinating—I was wondering how it could be done! Two comments: (1) B₄ appears in the definitions of all C_i but is not itself defined. (2) What is the degree of this equation in z? It looks very high, but I keep getting lost when I try to count the degrees (and I don't know the degree of B₄). Loraof (talk) 18:03, 11 June 2016 (UTC)

You are absolutely right. There is no B₄. Thanks! I'll correct it. The C's are computed from this.

$C_{0}+C_{1}x+C_{2}x^{2}+C_{3}x^{3}$

$=B_{3}(A_{0}+A_{1}x+A_{2}x^{2}+A_{3}x^{3}+A_{4}x^{4})$

$-A_{4}x(B_{0}+B_{1}x+B_{2}x^{2}+B_{3}x^{3})$

The degree of the equation is 5*12=60. Bo Jacoby (talk) 16:24, 13 June 2016 (UTC).

Also, is there a way to find out which root is the one we are looking for? Suppose we plot it against z, and find that there is a value below 1/2 and another value above 1/2 that both satisfy the equation. Does our desired value stand out in some way? Loraof (talk) 18:09, 11 June 2016 (UTC)

The equation $y^{12}=5$ has 12 complex roots, forming a regular 12-gon, and the equation $x^{5}=12$ has 5 complex roots forming a regular 5-gon, so of all the 60 differences $z=y-x$ only one is close to zero.

The equation

$0=F_{0}G_{1}-F_{1}G_{0}$

is computed by backwards substitution. Using

$G_{0}=-E_{0}F_{1}$

$G_{1}=E_{2}F_{0}-E_{1}F_{1}$

get

$0=F_{0}(E_{2}F_{0}-E_{1}F_{1})-F_{1}(-E_{0}F_{1})$

simplify

$0=E_{2}F_{0}^{2}-E_{1}F_{0}F_{1}+E_{0}F_{1}^{2}$

Using

$F_{0}=D_{0}E_{2}-D_{2}E_{0}$

$F_{1}=D_{1}E_{2}-D_{2}E_{1}$

get

$0=E_{2}(D_{0}E_{2}-D_{2}E_{0})^{2}-E_{1}(D_{0}E_{2}-D_{2}E_{0})(D_{1}E_{2}-D_{2}E_{1})+E_{0}(D_{1}E_{2}-D_{2}E_{1})^{2}$

simplify

$0=+D_{0}^{2}E_{2}^{3}+D_{2}^{2}E_{0}^{2}E_{2}-2D_{0}D_{2}E_{0}E_{2}^{2}-D_{0}D_{1}E_{1}E_{2}^{2}+D_{1}D_{2}E_{0}E_{1}E_{2}+D_{0}D_{2}E_{1}^{2}E_{2}-D_{2}^{2}E_{0}E_{1}^{2}+D_{1}^{2}E_{0}E_{2}^{2}+D_{2}^{2}E_{0}E_{1}^{2}-2D_{1}D_{2}E_{0}E_{1}E_{2}$

and so on. It isn't easy, but it is without round-off errors. Bo Jacoby (talk) 16:24, 13 June 2016 (UTC).