From Wikipedia, the free encyclopedia

Mathematics desk
< December 8	<< Nov | December | Jan >>	December 10 >

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.

Contents 1 December 9 1.1 Local extrema 1.2 Jian squares 1.3 XORing strings

[edit] December 9

[edit] Local extrema

If you have a function, how you can find the local min and max points, without looking at a graph? I know it involves finding the derivative71.218.18.209 (talk) 07:07, 9 December 2007 (UTC)

Solve analytically for the expression of the derivative, and then set it equal to zero to find your abscissa, usually x. Then, substitute the abscissa into the original equation, to find the ordinate, usually y. Titoxd^{(?!? - cool stuff)} 07:17, 9 December 2007 (UTC)

And I almost forgot, apply the second derivative test to make sure it really is an extreme value, instead of an inflection point. Titoxd^{(?!? - cool stuff)} 07:20, 9 December 2007 (UTC)

Not quite. A local extremum can come in any of three forms - somewhere the derivative (if it exists) reaches zero, somewhere the derivative fails to exist, or (if the function is defined on an interval) one of the endpoints. For instance, the absolute value function has a minimum at x=0, but the derivative isn't zero anywhere. You can't use the second derivative test where there is none, and it's misleading at the endpoints, so the more reliable test is to list all possible "critical points" and find the value of the function at each one. Black Carrot (talk) 15:36, 9 December 2007 (UTC)

Even then, you have to be careful if the function is not continuous on the whole interval. If you consider the cosecant function on the interval (0,2π) (except for x=π, where csc(x) is undefined), the derivative equals 0 at x=π/2 and x=3π/2, with csc(π/2) = 1 and csc(3π/2) = -1. Thus, it appears that we have a maximum at π/2 and a minimum at 3π/2, but a glance at the graph will reveal that this is incorrect. -GTBacchus^(talk) 20:50, 9 December 2007 (UTC)

This method is for local extrema. So, comparing values of extrema is not of much help. You may find examples like the last posed even for continuous functions. If you want to know whether such points are local minima or maxima, use a second-order criterion. For this case, second derivative is handy.

• local minimum
• local maximum

Pallida  Mors 23:17, 9 December 2007 (UTC)

[edit] Jian squares

What's a Jian square? They're mentioned in the Wikipedia article 384 (number) and, as far as I can tell, nowhere else on the Internet. A Google search for "Jian squares" returns only Wikipedia mirrors and a Google search for "Jian square" returns irrelevant results. I've tried searching for things like "Jian+factorial" but haven't had any luck with that method either. Info about the Jian square was added by Rich Farmbrough in this edit so it wasn't vandalism. I'll alert Rich about this conversation. I stumbled upon this article while finding out what a double factorial is. Graham87 13:07, 9 December 2007 (UTC)

This may not help much, but I believe it is actually a Jain square... Rich Farmbrough, 14:04 9 December 2007 (GMT).

Yes, see here. This info seems to have been leached from en:WP over time. Rich Farmbrough, 14:09 9 December 2007 (GMT).

Is a Jian square a special type of Most-perfect magic square? -GTBacchus^(talk) 20:53, 9 December 2007 (UTC)

Hmmm, it seems to be, according to Talk:Most-perfect magic square. There was a template for formatting these squares at Template:4x4 type square. Graham87 23:25, 9 December 2007 (UTC)

[edit] XORing strings

Given k binary strings of length n, I want to pick a subset of them so that they, when XORed together, result in the string s. Is that possible to do in a reasonable amount of time? (We may assume that there actually is a solution to be found.) —Bromskloss (talk) 21:30, 9 December 2007 (UTC)

This is equivalent to solving a system of linear equations over GF(2). In the absence of more specialized solution methods, any conventional solution algorithm (such as Gaussian elimination) ought to do the trick — just remember to do all the math modulo 2. —Ilmari Karonen (talk) 22:01, 9 December 2007 (UTC)

Specifically, here's some pseudocode based on Gauss-Jordan elimination over GF(2) that ought to do the trick:

• Let b₁, b₂, ..., b_n be (k+1)-bit strings, with b₁ consisting of the first bits of (s₁, s₂, ..., s_k, s), b₂ of the second bits, etc. (Note that the last bit of each b_i comes from the target string s.)
• Let i = 1, j = 1.
• While i ≤ n and j ≤ k+1:
  • If bit j of b_i is zero:   (pivoting)
    • Find h > i such that bit j of b_h is one. If none exists, increase j by one and try again.
    • Swap b_i and b_h. Now bit j of b_i is one.
  • For all h such that 1 ≤ h ≤ n, h ≠ i:   (row reduction)
    • If bit j of b_h is one, let b_h = b_h xor b_i.
  • Let a_i = j.
  • Increase both i and j by one and repeat.
• If a_i-1 > k, there is no solution. Otherwise a solution is (x₁s_a1 xor x₂s_a2 xor ... xor x_i-1s_ai-1) = s, where x_h is the last (k+1th) bit of b_h. This solution is unique if and only if i = k+1 (in which case, necessarily, a_h = h for all h ≤ k).

Note that, if the bitstrings b_i are long, you can optimize the algorithm somewhat by ignoring any bits lower than bit j; those will have already been processed, they won't change any more, and any useful information that could be found in them is already stored in a more convenient format in the array a. In particular, during the row reduction subloop, all bits of b_i lower than bit j will always be zero. —Ilmari Karonen (talk) 03:14, 10 December 2007 (UTC)

As a technical note, I once wanted to solve a variant of Lights Out (game) [1]. This puzzle results in such a linear equation with about a hundred variables. I used GAP (which was already installed on my machine) and after a few experiments with matrix inverses, it could indeed do it. – b_jonas 12:15, 12 December 2007 (UTC)

Why would you use a clothing retailer for that purpose? Using GAP instead might be more appropriate. -- Meni Rosenfeld (talk) 13:46, 12 December 2007 (UTC)

Indeed. It would have been easier.  :) – b_jonas 10:30, 14 December 2007 (UTC)