Mathematics desk
< January 13	<< Dec \| January \| Feb >>	January 15 >

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.

January 14[edit]

Topology terminology[edit]

Years ago, I was chatting with a friend (a maths PhD) about a topic in his specialty, topology: the subject was surfaces that could be turned inside out (?) to form other shapes without requiring that the surface be torn or otherwise similarly mangled. The only example I remember clearly (if I remember any clearly) was that of turning the shape of a doughnut into that of a drinking mug. What's the normal term used for the study of topological transformations of shapes? Nyttend (talk) 02:49, 14 January 2016 (UTC)[reply]

PS, I just discovered Homeomorphism. Is that the term I'm looking for, or does it merely describe what happens during the study of topological transformation of shapes? Nyttend (talk) 03:08, 14 January 2016 (UTC)[reply]

See Continuous deformation (or Homotopy). It's an old saw that topologists can't tell a coffee mug from a doughnut. -- ToE 03:11, 14 January 2016 (UTC)[reply]

Your friend might have had "turning the sphere inside out" (search it!) in mind as a nice example. In the 1950's (I think) Stephen Smale found that it is possible, see Sphere eversion. YohanN7 (talk) 11:22, 14 January 2016 (UTC)[reply]

The doughnut-to-mug deformation is a classic example: the two surfaces are topologically equivalent. What's less obvious is that a doughnut shape with a single puncture in the surface can be turned inside out through the puncture. AlexTiefling (talk) 11:36, 14 January 2016 (UTC)[reply]

Just to clarify: yes, we say a coffee mug and a doughnut are homeomorphic. We also say there exists a homeomorphism that sends one to the other. But I don't thing "I'm a topologist specializing in homeomorhisms" is really a think someone would say. Most any topologist deals with homeomorphisms often, so it's not a clear sub-field delimiter. The sub-divisions of topology are traditionally higher order - algebraic topology, point set topology, low dimensional topology etc., and all these subfields use/construct/prove-the-existence-of homeomorphisms frequently. Knot theory is one pseudo-exception: it can be classed as a subfield of topology, but there is much more interest in homotopy than homeomorphism. The reason is interesting: all knots are homeomorphic to the unknot (i.e. a circle or any closed loop), so we need a more refined notion of "same topological shape basically" to distinguish a trefoil knot from a figure eight knot. Continuous deformation is required for homotopy, but not homeomorphism. Intuitively, cuts and tears are allowed in in a homeomorphism, but you have to glue them back together the same way at the end. In homotopy, tears are not allowed. So any two things that are homotopic are also homeomorphic, but there are plenty of things that are homeomorphic but not homotopically equivalent, an example being the two knots linked above. SemanticMantis (talk) 16:45, 14 January 2016 (UTC)[reply]

It is also true that if you take a torus and poke a small hole in it, you can (in principle) turn it inside out without tearing by pushing it through the hole. If you do this (and then patch up the hole), what you get is still a torus, but the lines of latitude and longitude (I mean, the lines that go around the small circle and the lines that go around the big circle) have changed places. --JBL (talk) 15:28, 15 January 2016 (UTC)[reply]

Pairwise combinations from binary strings[edit]

Recently, I stumbled upon an interesting question.

Let S_i denote a collection of binary strings each having N bits. Lets s_i,j denote the j-th bit in the i-th string.

What is the minimum number of strings, M, necessary for such a collection to have the property that for all (j,k), j≠k each of the following is true:

There exists a such that s_a,j = s_a,k = 0.
There exists b such that s_b,j = s_b,k = 1.
There exists c such that s_c,j = 1 and s_c,k = 0.
There exists d such that s_d,j = 0 and s_d,k = 1.

Essentially, we are looking for all possible pairwise combinations of bit values to be present within the collection of strings.

I was told without proof or reference that $M\approx 4\log _{2}(N)$ . By Monte Carlo testing, I concluded that this is approximately correct, but probably represents either a large N limit or an upper bound rather than an exact value. The Monte Carlo sampling found this estimate can overstate the true minimum value by at least a few. Nonetheless, it seems like a pretty good estimate, and I am curious where it comes from? Can anyone point to the origin of this estimate, or explain how it is derived? I'm curious if a proof might also offer a constructive strategy for generating a minimum set of strings. Lastly, I am wondering if there is similar way to express the minimum number of strings needed to satisfy the above conditions not once but at least p times for all (j,k)? Dragons flight (talk) 13:27, 14 January 2016 (UTC)[reply]

The minimum is, of course, M=2 for N≥4 : just take two strings starting with '0011...' and '0110...'. For N less than 4 the required set does not exist. --CiaPan (talk) 14:56, 14 January 2016 (UTC)[reply]

Oh, and if you mean an arbitrary set of strings, then there is no M that guarantees all four conditions can be satisfied: if the set contains a string consisting of zeros only, it will not satisfy condition 2. CiaPan (talk)

The log₂(N) might be a hint to use the binary representation of j and k. After all, j ≠ k iff at least one bit in their binary representation differs. In the definition of the j-th bit I'll assume zero-based numbering from the left. As an example, the solution for N = 8 would contain the strings

00000000, 11111111 (to handle requirements 1 and 2)

01010101, 10101010 (bit #0 of j, not(bit #0) of j)

00110011, 11001100 (bit #1 of j, not(bit #1) of j)

00001111, 11110000 (bit #2 of j, not(bit #2) of j)

In general this takes

M=2+2\lceil \log _{2}(N)\rceil

strings. Egnau (talk) 15:08, 14 January 2016 (UTC)[reply]

For the string s_j=00000000 (whatever j is) there is no such position p which makes a s_p,j = 1. So the given set does not satisfy conditions. --CiaPan (talk) 18:18, 14 January 2016 (UTC)[reply]

Condition 2 doesn't say that s_b,j = s_b,k = 1 must hold for each string, it says that it must hold for at least one string. In my example, condition 2 is satisfied by choosing b such that s_b = 11111111. Egnau (talk) 19:54, 14 January 2016 (UTC)[reply]

(ec) Yes, it does say that. It is explicitly said: 'for all (j,k), j≠k each of the following is true' – and conditions 1..4 follow; so they all must hold for each pair of strings. What you say could be expressed like 'for each j there exists k such that each of the following is true' or may be 'for each of the following there exists (j,k) such that s_j and s_k satisfy it.' But these requirements are weaker than those defined by Dragons flight. --CiaPan (talk) 21:20, 14 January 2016 (UTC)[reply]

I think I see your mistake. In the problem description j,k are bit positions and i,a,b,c,d are string indices, not the reverse. Feel free to ~~strike~~ all your previous comments if they depend on misreading the notation. Egnau (talk) 22:28, 14 January 2016 (UTC)[reply]

I think you are right. I was misled by a combination of conveyed wisdom (the equation) and a Monte Carlo that made that look plausible, but apparently wasn't getting all that close to the optimal solution. Thanks. Still curious about the extension to at least p copies of the criteria, but that doesn't seem very approachable to me. Dragons flight (talk) 21:09, 14 January 2016 (UTC)[reply]

Note that I never claimed that my solution was optimal. About the extension, one possible approach is to consider M random strings. For each pair (j,k), we expect each condition to be fulfilled M/4 times. I think that it's possible to find an M that has a positive probability of success for all pairs and all conditions, which would imply the existence of a solution. First, get a bound on the tail of a B(M, 1/4), and use Boole's inequality to get a probability bound that applies to all (j,k) and all conditions even if the events aren't independent. Egnau (talk) 22:52, 14 January 2016 (UTC)[reply]