Wikipedia:Reference desk/Archives/Mathematics/2009 February 20
Mathematics desk | ||
---|---|---|
< February 19 | << Jan | February | Mar >> | February 21 > |
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. |
February 20
editAnalysis on an interesting function
editHi there - just finished a last bit of work and was wondering if anyone extremely kind with a little time to spare could spot anything stupid I've done in the process (highly likely) - I may well have botched it up so pull no punches;
If is defined by for and . We define .
Sketching f0, f1 and f0+f1 as follows: Media:graphfunction101.png
Showing that, for each , converges: if I've drawn my graphs right, the maximum value attained is must be less than or equal to (less than in this case) the sum of the maximum values of each fn, i.e. and so since the sum is monotonically increasing & bounded must converge.
Defining as , we want to show that f is continuous everywhere. By the definition of continuity I'm using we want ; then . Since we know (or I'm fine showing) the fn are all convergent, it seems to be simply a matter of swapping the sum and the limit - I'm not completely sure how to prove it's alright to do this? Once that's done we have continuity of f.
Lastly, we want to know where f is differentiable - it seems the non-differentiable points are and so I'd say the function is non-differentiable over the dyadic rationals , so differentiable over - is this correct? If so, is there any way to make the argument more rigorous than 'by inspection' or do I have to go back to the fundamental definition of 'differentiable'?
Obviously I fully understand you're not here to just 'check my working' and I've asked/rambled an awful lot here, but any small help would be greatly appreciated if you have any time spare at all - thanks very much! Also, I tried to find the rules on uploading/linking to images but I had no luck - apologies if I broke any rules! Thanks very much again - Mathmos6 (talk) 04:36, 20 February 2009 (UTC)Mathmos6
- If I'm not missing something, uniform convergence and its application to continuity could help you show that is continuous. —Bromskloss (talk) 08:10, 20 February 2009 (UTC)
- Correct, you have a normally convergent series of continuous functions, that is, verifying
- ,
- which implies the uniform convergence of the series to a continuous function (this is the so called Weierstrass test). It's a general fact: in any Banach space a normally convergent series (that is, such that the series of the norms is finite) is convergent (here we deal with the particular case of , the space of bounded continuous functions on endowed with the uniform norm). Going back to your function, notice that it satisfies the functional equation:
- .
- I wish to show you that this equation tells you everything about your function, existence included. To start with, f is the only solution among bounded functions (of course, if you allow unbounded functions, there are infinitely many solutions, for instance ). To see it, consider the Banach space of all bounded functions on , again with the uniform norm. A function is a solution of the functional equation if and only if it is a fixed point of the contraction on , defined by . The Banach fixed point theorem immediately tells you that there exists exactly one bounded function satisfying the functional equation. It tells you more: since this contraction is an affine map, the usual sequence of iterations converging to the fixed point is a series (your series, indeed). A standard way to get informations on the solution x of a fixed point equation of a contraction is the following: if C is a closed, nonempty T-invariant set of X (meaning that ) then, just by the unicity, . This way the equation immediately tells you that your fixed point f is continuous, 1-periodic, even, positive, and that : all these properties correspond to suitable closed nonempty invariants sets of T (for instance: to get a bound on the uniform norm, you may observe that implies ; so in particular choosing you have that the closed ball of center 0 and radius 2/3 is T invariant, therefore contains the fixed point. You can prove all this also from the series, of course). With a little more accuracy you can compute exactly . By the same method you can show that f has a modulus of continuity of the form
- (Note that this just means: for all x and y; unfortunately at the moment the wikipedia article on modulus of continuity does not give the standard definition). Anyway, try it, and evaluate the constant! Then, is not a Lipschitz function, for it has a right derivative at 0 equal to infinity, as you said. To prove this, consider the Dini derivative
- One advantage of the Dini derivatives is that they always exist, although they have quite a poor calculus. Their poor calculus is however enough to get, again from the functional equation:
- .
- If you take x=0 you get the following odd equation (in the extended real line): . Since and , we conclude . So actually it is the right derivative (the limit inferior is a limit): . Now consider the set where the right derivative of f is :
- We have seen that ; from the 1-periodicity we have ; from the above relation about the Dini derivatives in x and 4x, we also have , and we conclude that E contains all dyadic rationals. They also have the left derivative equals to , by the analogous argument. Do not hesitate to ask if you need further details.--pma (talk) 21:27, 20 February 2009 (UTC)
- Fascinating! As a matter of interest, you say "This way the equation immediately tells you that your fixed point f is continuous, 1-periodic, even, positive, ...", "With a little more accuracy you can compute exactly ", and "By the same method you can show that f has a modulus of continuity of the form
- ". How would you accomplish these? Obviously it's quite a long list so if you don't have the time don't worry about it, but I'm particularly interested in seeing how you would show it's continuous, 1-periodic, even and positive using the method you gave an example of (apologies, my knowledge on Topology is limited but I'd be very happy to read up if you could point me in the right direction!), and also where you obtained from? The information you gave was extremely helpful and very informative, thanks a lot! Mathmos6 (talk) 13:30, 25 February 2009 (UTC)Mathmos6
- In fact the computation of is really elementary. Start from the functional equation and plug it into itself: you get:
- Now the function , as shown by your graph, has maximum value 1/2 in the whole middle interval [3/8,5/8]. ON the other hand, the function is periodic of period 1/16. As a consequence, the maximum value of f is atteined in the middle interval, an we have y=1/2+y/16: here is where y=8/15 comes from. Moreover, you can write an equation for the first maximum point of f in [0,1]: it turns out to be 2/5. You can even characterize the set M of all maximum points of f in [0,1]: it is a Cantor set, precisely, it is made by the union of four copies of itself reduced by a factor 1/16, and then translated by resp. 6/16, 7/16, 8/16, 9/16. In one formula: (remember that for sets A and B of numbers, A+B denotes their Minkowski addition, the set of all a+b with a in A and b in B). Equivalently, M is the set of all reals number in [0,1] whose hexadecimal expansion only has the digits 6,7,8,9 (the first one, 2/5, is of course 0.666...) It turns out that f is not differentiable at the maximum points, and at the local maximum points neither. Maximum points, and points of local maximum also, are an uncountable set; till of measure zero. I do not see an easy way to decide whether f is differentiable at least in a point. As far as I see, it may have no points of differentiability, or on the contrary, it may be differentiable almost everywhere, even with f'(x)=0 almost everywhere. I only checked that it is NOT of bounded variation. Maybe somebody here knows the answer, or as an idea.
- As to the other question, maybe a good starting point is the Banach contraction theorem. If you understand it for functions of one real variable, you got it in the general case of contractions on complete metric spaces. You also need to know that the space is a complete metric space. I can not enter into all details of course (but you can always post a new question on a specific point!). The remark I mentioned is very simple: the fixed point of a contraction on a complete metric space belongs to every closed, nonempty, and T-invariant (the reason is that is also a contaction on a non-empty complete metric space, so has a fixed point, which is also the unique fixed point of T in X. Or equivalently, if you think to the proof, just start the iteration with a point : then the theorem states that converges to the fixed point of T: but since the whole sequence is in C, and being C closed, the limit also belong to C). As I said, almost all the properties of the function that I listed can be easily proven with the series, but it could be instructive to use the invariant set method.
- Example: the set is closed (this is an important fact: the continuity is preserved by uniform convergence). The above map takes continuous functions into continuous functions (quite obvious: if u(x) is a continuous function of x so is . Obvious consequence: the fixed point of T on is also in . You can prove all properties in one strike considering the subset C of all continuous functions with uniform norm less than or equal to 2/3, that are even, 1-periodic, subadditive, positive and that satisfy , and proving that C is a closed T-invariant non-empty set. It is not so difficult; remember that the intersection of closed set is closed. For the last, you need to chose the parameter suitably (like the number R for the norm). Then you also have for all x and y, since f is subadditive and even , showing that is a modulus of continuity of f. --pma (talk) 18:13, 26 February 2009 (UTC)
Setting up Maekawa's Algorithm
editFor an assignment, I had to come up with an algorithm to set up Maekawa's Algorithm. You don't need to read the algorithm. For N elements, I had to come up with N sets of K elements such that for any two sets you pick, at least one element will be shared between them. In other words, every set intersects with every other set. Now that I'm done and I've submitted it, I thought I'd Google for what the "best" algorithm is and, surprisingly, I can't find one anywhere. So, I have two questions:
1) What is the "best" algorithm for doing this? Does it have a name that I can Google and find? Keep in mind that by "best", I am implying that it is an algorithm that is best when implemented on a computer. So, big-O complexity is what is normally used to rate algorithms.
2) I know I didn't invent a new algorithm. So, does it have a name? To do this, I have to describe the algorithm. I do that below. I hope I can get a collapse box to work properly so I don't flood the RD:
Begin with N sets of K elements, all empty (meaning all elements are null). Assume N=7 and K=3 for this example. Set SNi*k to [0, ik+1, ik+2] for i=0 to 2. So, S0=[0,1,2], S3=[0,3,4], S5=[0,5,6]. I just noticed that there is an error in my description and result. I'll have to go back and fix that on my submission. All I did was fill the first element with 0 and then fill the rest, in order with 1, 2, 3, 4, 5, 6.
Now, take any empty set (S1 for example). Si must contain i, so put a 1 in S1. Then, create an array of N boolean values, all false. For every Sj that intersects with S1, take each element e of Sj and set Ue to true. So, S0 intersects because it has a 1. Set U0=true, U1=true, U2=true. No other sets intersect. This process will, from now on, be called "set intersects in U." After setting intersects in U, find any Sj that doesn't intersect with S1. S3 doesn't. Pick an element e in S3 such that Ue is false. U0 is true, so that won't work. U3 is false. Add 3 to S1. Now, S1 is [1, 3, null]. Set intersects in U again. Because S1 is not full, find another set that doesn't intersect (S5). Pick an e in S5 such that Ue is false. 5 will work. Add 5 to S1.
Repeat for S2. Add 2 to S2. Set all U to false. Set intersects in U. Find a set that doesn't intersect. Pick an e such that Ue is false. Set intersects in U. Pick another e. Then, repeat for the next empty set. In the end, you will have N sets such that each one will intersect, assuming that it is possible for the given N and K values to start with.
Thanks. -- kainaw™ 05:01, 20 February 2009 (UTC)
- Could you describe the problem you were trying to solve more carefully? It seems trivially solvable to me - simply give all of the N sets the same element. Then all pairs of sets share that element, and the other K-1 elements are irrelevent. —Preceding unsigned comment added by Maelin (talk • contribs) 06:18, 20 February 2009 (UTC)
- That would work if all you wanted was N sets. However, this is for Maekawa's Algorithm. Each of the N elements must be located in the sets. To do that fairly, consider N=7 and K=3 (7 sets of 3 elements). There are 7 unique elements to place in 21 positions, so each of the 7 unique elements should appear 3 (21/7) times and every set should intersect every other set. -- kainaw™ 06:22, 20 February 2009 (UTC)
- Starting from K, inspection suggests that you want E elements where E = (K * (K-1))+1 and where N = E. Thus K=3 gives 7 elements and 7 sets. K=4 gives 13 elements and sets. No idea on the name though, but you may find clues at (sequence A002061 in the OEIS). -- SGBailey (talk) 10:38, 20 February 2009 (UTC)
- Actually, N and K are given. The goal is to create N sets such that each element shows up in K sets and every set intersects every other set. For example, given 0, 1, 2, 3, 4, 5, 6, N is 7. If K=3, you can use the sets: 012 034, 056 135 146 236 245. Every element appears in 3 sets and each set intersects every other set. Imagine if you were given something like 200 elements to start with. Coming up with the sets would be difficult to do by hand, which is why an algorithm is needed. -- kainaw™ 18:41, 20 February 2009 (UTC)
Unreachable chess positions
editWhat chess positions are unreachable by any legal series of moves from the starting position, besides those that would require an illegal amount of material, those that have both kings in check or the same king in check by two knights, and those that have pawns on the first or eighth rank? NeonMerlin 05:57, 20 February 2009 (UTC)
- Any where the pawns have changed columns without an appropriate number of opponent pieces having been captured. -- SGBailey (talk) 07:02, 20 February 2009 (UTC)
- Those that have two bishops from the same side on the same colour squares. --Tango (talk) 10:41, 20 February 2009 (UTC)
- That's easily possible, with promotions. You can't do it with all pawns still on the board though. Algebraist 11:10, 20 February 2009 (UTC)
- Good point. I always lose long before any pawns get promoted! --Tango (talk) 12:25, 20 February 2009 (UTC)
- Retrograde analysis might be of interest. —JAO • T • C 13:48, 20 February 2009 (UTC)
- You can't have any pawns behind the initial starting position. Also, assuming you always promote them when they reach the end, you can't have any pawns there either. StuRat (talk) 14:39, 20 February 2009 (UTC)
- The OP already said that one - you're using my trick of not reading the question before answering it! --Tango (talk) 15:26, 20 February 2009 (UTC)
- But they're so much easier to answer if you don't read them fully. :-) StuRat (talk) 19:21, 20 February 2009 (UTC)
- You don't actually have a choice about whether to promote. Your choice is limited to what to promote to, which must be a piece (pawns are not pieces!) and can't be a king. Of course it's extremely rare that it would be to your advantage not to promote, but theoretically it could happen; it might be that your opponent is going to win anyway, even if you get the queen, but if you leave it a pawn he might stalemate you on his next move.
- Here's a question I don't know the answer to: Is there any situation in which, if you could leave a pawn unpromoted on the eighth rank, your opponent would have to stalemate you, or must you depend on a blunder? Full credit if his only choice, other than stalemating you, is to give up his winning position. --Trovatore (talk) 20:25, 20 February 2009 (UTC)
- While pondering Trov's question I was considering this position: kb6/p1P5/Kp6/1P6/8888 with White to move. It doesn't quite answer the question, but the only moves White has (including both possible "nonpromotions") which don't soon force a stalemate is a B or N underpromotion at c8. c8N might actually be an interesting game, but then I looked at my original position and said, what was Black's last move? Baccyak4H (Yak!) 21:16, 20 February 2009 (UTC)
- But they're so much easier to answer if you don't read them fully. :-) StuRat (talk) 19:21, 20 February 2009 (UTC)
a | b | c | d | e | f | g | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | b | c | d | e | f | g | h |
- @Trovatore: A very late answer, but Hauke Reddmann composed a position in 2017 that answers your first question (but without the full credit): q7/2P5/8/8/8/8/p1r5/K1k5. 1.c8=P! is immediate dead position (but 1.c8=any? Qf3!). Double sharp (talk) 19:24, 5 February 2023 (UTC)
- Not immediately seeing what's wrong with 1.c8=P Kd2. --Trovatore (talk) 21:10, 5 February 2023 (UTC)
- @Trovatore: Still a stalemate, the a2-pawn covers b1. The idea is that a2, b1, and b2 are all guarded twice over, so Black cannot unguard them with a single move; but Black also cannot threaten a1 as the c8-pawn blocks the queen's route to h8. Double sharp (talk) 22:44, 5 February 2023 (UTC)
- Oops, I think I color-flipped that pawn in my head. --Trovatore (talk) 02:19, 6 February 2023 (UTC)
- @Trovatore: Still a stalemate, the a2-pawn covers b1. The idea is that a2, b1, and b2 are all guarded twice over, so Black cannot unguard them with a single move; but Black also cannot threaten a1 as the c8-pawn blocks the queen's route to h8. Double sharp (talk) 22:44, 5 February 2023 (UTC)
- Not immediately seeing what's wrong with 1.c8=P Kd2. --Trovatore (talk) 21:10, 5 February 2023 (UTC)
- @Trovatore: A very late answer, but Hauke Reddmann composed a position in 2017 that answers your first question (but without the full credit): q7/2P5/8/8/8/8/p1r5/K1k5. 1.c8=P! is immediate dead position (but 1.c8=any? Qf3!). Double sharp (talk) 19:24, 5 February 2023 (UTC)
- I don’t think it’s legally possible for the king to be in check from three different units of any kind. Because in a single move it appears you can only put a king in check from two pieces: one that you move, and one entry point you create by moving.
- It’s also impossible to have 6 pawns all in the same column on the side of the board, and two in another column. Because that would have required capturing 16 pieces from the opponent. Similarly there are a bunch of other impossible conditions relying on the fact that pawns can only change column by capturing a piece. GromXXVII (talk) 23:53, 20 February 2009 (UTC)
- The last statement is not true. Pawns can also change file by capturing a pawn. --Trovatore (talk) 00:03, 21 February 2009 (UTC)
- Now, now, this is the Ref Desk, no pedants allowed! --Tango (talk) 00:06, 21 February 2009 (UTC)
- You are aware that the word piece is used both in an inclusive sense (that's the one used in the official FIDE rule book) and in a sense excluding pawns (very common in chess literature), and also often to include only knights and bishops (when discussing material imbalance)? Here, Grom used it in the same sense as FIDE does. —JAO • T • C 10:29, 21 February 2009 (UTC)
- The last statement is not true. Pawns can also change file by capturing a pawn. --Trovatore (talk) 00:03, 21 February 2009 (UTC)
Stuck with a PDE (Schrödinger)
editHi! I've been looking at Hylleraas old solution to the electronic Schrödinger equation for Helium. (First multi-electron calculation accurate enough to prove quantum theory would work for multi-electron problems as well as the hydrogen atom). I've managed to repeat all the work, except for one thing. I'm a bit stuck here, getting from (5) to (6). Apparently, lambda gets moved over, and both sides get multiplied by r1r2r12 and psi and then integrated, so that the normalization condition (second row of (6)) can be applied to the right side. What I don't quite get is how the first row of terms in (5) turns into the squares of the first-derivative like that. What am I missing here? --Pykk (talk) 20:31, 20 February 2009 (UTC)
A polar closure property
editLet X and Y be sets. A polar from X to Y is a map p from the power set of X to the power set of Y that satisfies
for any collection of subsets of X. The dual of p is the map given by
- .
Some facts about polars:
- A polar is antitone: .
- The dual of a polar is a polar. If q is the dual of p then p is the dual of q. In this case we say that p and q are a polar pair.
- p and q are a polar pair p and q are antitone and and are extensive: .
- and .
- and are closure operators in X and Y respectively.
Now let . I'm trying to see that
for any collection of subsets of X. This must be very simple, but I'm missing it. — merge 21:26, 20 February 2009 (UTC)
- It's a matter of unwinding the definitions. Let be an element of the set on the LHS. Then you show it must also lie in the set on the RHS. (This direction is true for any closure operation.) Similarly the other way around, you start with in the set on the RHS and show it must lie on the LHS. All you need is the definition of ; you don't need to use the polar property.Ctourneur (talk) 20:19, 21 February 2009 (UTC)
- Thanks, but I'm still missing it. Right includes left is obvious. In the other direction we need
- or in other words
- ,
- and I don't see why this should be so. — merge 21:20, 21 February 2009 (UTC)
- Thanks, but I'm still missing it. Right includes left is obvious. In the other direction we need
- Let X be a topological space in which singletons are closed, and let p take a set A to the interior of the complement of A (i.e. the biggest open set in the complement of A). Then qp(A) is just the closure of A in the topological sense, right? Now we can take just two sets A and B, which have the same closure, but whose intersection is empty, and this is a counterexample.Ctourneur (talk) 21:57, 21 February 2009 (UTC)
- Wouldn't you need the intersection of interiors to be the interior of the intersection in order for p to be a polar? — merge 23:08, 21 February 2009 (UTC)
- You're right (of course). And (unless I'm making another mistake) that means that the topology actually has to be discrete, so those examples aren't interesting.
- Maybe I should stop pretending to help, but here's another idea. A polar can be specified by defining for all x, and this can be done arbitrarily; then you extend p to arbitrary sets by using the polar property.
- So for example, there is a polar on the set defined by for any . Then for any larger set, .
- Now , while .
- If we take , I think we have our contradiction.
- (Or perhaps I am wrong again.) Ctourneur (talk) 04:43, 22 February 2009 (UTC)
I think you're right. I'd begun to think along similar lines. This material is from pp. 85–86 of Schechter. Another candidate for the errata, I guess. It's a very strange error for him to make because he states the above property along with all the others and notes that it applies to polar closures but not closures in general. — merge 13:10, 22 February 2009 (UTC)
- I'm just guessing, but maybe the definition of polar is sometimes taken to include that:
- It seems like that would fix the problem (by your work above).
- Anyway, interesting question. Thanks. Ctourneur (talk) 13:54, 22 February 2009 (UTC)
- Thanks for your help and ideas! The author applies these results to generalized orthogonality relations and thence to Riesz and Hilbert spaces. In this situation one has . I'll try to contact him and update the thread with any response. — merge 18:13, 22 February 2009 (UTC)
I believe the author is correct. To prove the more difficult inclusion, note for any polar p, . --Alumbrosh (talk) 20:40, 29 September 2009 (UTC)