A non-Euclidean characterization of convexity: proof of theorem

We give here the proof of the theorem and corollary stated in "A non-Euclidean characterization of convexity".

Theorem. For any X in Rⁿ

H_wave(X) = X U int(H_convex(X)),

where H_wave(X) = U_r≥0B_r(B_r(X) \ Rⁿ) \ Rⁿ, B_r(A) is the union of all closed balls of radius r centered at points in A, int(A) is the interior set of A and H_convex(X) is the convex hull of X.

Proof.

1. X U int(H_convex(X)) is included in H_wave(X): obviously X is included in H_wave(X). If x is in int(H_convex(X)), we can find an n-simplex σ around x that is entirely included in H_convex(X). From the definition of a convex hull, for each face f_i of σ there must be some x_i in X such that x_i lies in the interior of the half-space delimited by the f_i and not including x. Consider now an arbitrary ray h departing from x: h will intersect some face f_i in the manner depicted below.

Following the variable naming convention of the figure, if we set r(h) = (a²+b_i²)/2a then for any point y in h dist(x_i,y) > r(h) → dist(x,y) > r(h). It can be seen that the values r(h) are upper bounded by some r, as we have only finitely many b_i's and a is bounded by the diameter of σ; and it follows that x belongs to B_r(B_r(X) \ Rⁿ) \ Rⁿ, since all points of Rⁿ at a distance greater than r from every point of X must also be farther away than r from x.

2. H_wave(X) is included in X U int(H_convex(X)): Let x be a point outside X U int(H_convex(X)). By Hahn-Banach Separation Theorem, there is a hyperplane π separating x from int(H_convex(X)), which implies that all points of X are included at one of the closed half-spaces delimited by π. Let h be the ray normal to π with origin in π, passing through x and moving away from X.

For any r ≥ 0, the point y in h at distance r from x (in the direction away from X) verifies that dist(x',y) > r for every x' in X U int(H_convex(X)); this is so even in the case where x belongs to the boundary of H_convex(X) and hence lies directly on π. So for every r ≥ 0 x is in B_r(B_r(X) \ Rⁿ) and thus does not belong to H_wave(X).

Corollary. cl(H_convex(X)) = ∩_r>0H_wave(B_r(X)), where where cl(A) denotes the topological closure of A.

Proof. If x is in H_convex(X), then for any r > 0 x is also in int(B_r(H_convex(X)) = int(H_convex(B_r(X)), which is included in H_wave(B_r(X)). Conversely, if x does not belong to cl(H_convex(X)) then by Hahn-Banach Separation Theorem there is a hyperplane separating x and cl(H_convex(X)), and a fortiori separating x and cl(H_convex(B_r(X))) for some r > 0; but the latter set is a superset of H_wave(B_r(X)), hence x does not belong to this either.

Liquid s

We Spaniards have a curiously stubborn inability to correctly pronounce foreign words beginning with /s/+consonant, such as, for instance, "Spain", which invariably we utter as Ehs-pain, to the amusement of English speakers. It is only by training ourselves that we manage to get rid of that spurious "e" preceding the "s" sound, but somehow seems like adding it comes naturally to Spanish speakers. How come we universally apply this phonetic transformation /s/+consonant > /es/+consonant without having been explicitly taught to do so?

In all Iberian Romance languages (and seemingly early stages of other Romance languages like French), Latin words beginning with the so-called liquid s ("s líquida") evolved to include a supporting "e" preceding the "s" sound, vg. scribere > escribir, spatium > espacio, etc. As a result, Spanish (and Portuguese, Catalan, etc.) lexicon does not have any words beginning with /s/+consonant, and this phonetic construct just does not belong in Spanish phonotactics. Consequently, when confronted to it, the Spanish speaker will try a transformation to a valid sequence within the Spanish phonetic system. The question is why the transformation /s/ > /es/ is invariably chosen instead of other valid candidates like /s/ > /as/, /s/ > /is/, etc. I don't have a definite answer, but the following hypotheses come to mind:

Hyp1. Somehow we have been taught to read "s"+consonant (at the beginning of a word) as /es/+consonant, in the same way as we learnt how to read out other letter combinations, regardless of whether they correspond to actual words or not.

Hyp2. This is just a manifestation of the ancient phonetic rule that wiped Latin liquid esses: much as our folk were aware of that transformation we also are and thus use it to deal with alien phonetics.

Hyp3. /es/+consonant is more frequent in Spanish than the formations with the rest of the vowels and diphthongs, so we choose it following a sort of Bayesian argument.

Hyp4. We are influenced by the pronunciation of related Spanish words, which in most cases carry the supporting /e/ as a result of the ancient phonetic transformation from Latin liquid s. So, when first confronted to the word "state", the Spanish words "estado", "estatal", etc. appear as associations in the mind of a Spanish speaker, which induces the application of the /s/ > /es/ rule.

Hyp5. The only plausible candidate transformations are of the form /s/+consonant > vowel+/s/+consonant or /s/+consonant > diphthong+/s/+consonant. Of the five vowels and about a dozen diphthongs in Spanish, /e/ is perceived by speakers as a neutral or default vocalic sound (a role possibly played by /ə/ in English), hence we choose it instead of the others.

Hyp6. /es/ is perceived by the Spanish speaker as the perceptually closest construct to the ideal /s/. That is, [espein] is perceived as closer to [spein] ("Spain") than, say, [aspain].

A short discussion of each hypothesis:

Hyp1. This does not look much reasonable, since Spaniards' reading learning systems certainly never deal with words beginning with the letter "s" plus a consonant, and it is unlikely that most Spanish infants are exposed to foreign words outside their formal reading training and taught to pronounce them by some adult.

Hyp2. Again, this does not seem to hold water. Phonetic rules are not part of a language transmitted knowledge: infants are not actively taught the language, merely exposed to it, so all that they can acquire during the process are the results of such phonetic rules. The illusion of a phonetic rule A→B being transmitted from generation to generation and slowly applying their way to the sounds of a language stems from the dynamics of coexisting subpopulations favoring either A or B. Once A has been completely removed, no remnants of the rule persist on future speakers' minds. The elimination of Latin liquid s having completed centuries ago (possibly even before the formation of Spanish), we cannot invoke such ancient process to explain the current phenomenon.

Hyp3. This is not an entirely illogical argument, but its cogency is hard to estimate. Certainly /es/+consonant is much more frequent in Spanish than the rest of candidates, but not overwhelmingly so.

Hyp4. This hypothesis is very plausible and, in my opinion, must play a role at least in some cases, those where obvious equivalent words exist in Spanish. The problem is that the rule is also applied when there are no equivalent Spanish words to resort to, as I have verified by challenging people without knowledge of foreign languages to pronounce /s/+consonant-beginning words without similar-looking correlates in Spanish: it was also /e/ in those cases that was added to the pronunciation.

Hyp5, Hyp6. These explanations are very similar but show some differences: Hyp5 presents the case of a speaker trying to pronounce no vocalic sound and instead failing and uttering the default /e/, while in Hyp6 the speaker is trying to mimic a previously heard sound. Hyp6 is backed by examples of comparable situations in other languages, like the notable case of English pronunciation by Japanese speakers, featuring a kind of vowel-inserting transformation called anaptyxis (for instance, "strike" is pronounced something like [sutoraiku]). However, I lean towards Hyp5, because the /s/ > /es/ phenomenon also shows when reading a word rather than hearing it, even among speakers with negligible exposure to foreign languages, as I commented above. In favor of Hyp5 there is also the fact that the spurious /e/ is also included in a more exotic context, those of African words beginning with /n,m/+consonant, like Ntutumu, Nguema, Mbasogo (common personal names in the former Spanish colony Equatorial Guinea), which current Spaniards almost exclusively access to in written form.

I would love to know others' opinions on this issue --particularly from those with expertise in Phonetics.

Strict weak ordering extensions

A strict weak ordering (swo for short) is a binary relation < on a set A such that its complementary relation ≥ = AxA − < is a total preorder (reflexive, transitive and such that x ≥ y or y ≥ x, or both, for all x, y in A).

We introduce the notion of an extension to a strict weak ordering: Given <_A a swo on A, a swo extension of <_A to B, where B is a set disjoint with A, is a pair of relations <_A→B from A to B and <_B→A from B to A for which there is some swo <_AUB on AUB such that <_A = <_AUB ∩ AxA, <_A→B = <_AUB ∩ AxB, <_B→A = <_AUB ∩ BxA.

Theorem. (<_A→B,<_B→A) is a swo extension of <_A iff for all a, a' in A, b in B.

1. a <_A→B b → not(b <_B→A a),
2. not(a <_A→B b) and not(a' <_A a) → not(a' <_A→B b),
3. not(b <_B→A a) and not(a <_A a') → not(b <_B→A a').

Proof. If (<_A→B,<_B→A) is a swo extension of <_A, 1, 2 and 3 follow trivially from the properties of a swo on AUB. As for the converse, let us define the binary relation <_B on B as follows: b <_B b' iff there is some a in A such that at least one of the following two conditions hold:

1. not(a <_A→B b) and a <_A→B b',
2. b <_B→A a and not(b' <_B→A a) .

We will prove that <_AUB = <_A U <_A→B U <_B→A U <_B is a swo on B by showing that ≥_AUB = (AUB)x(AUB) − <_AUB is a total preorder. In the following we will consider x, y, z in AUB:

• Reflexivity (x ≥_AUB x): if x is in A, reflexivity follows from the properties of <_A. If x is in B and x <_AUB x, there would be some a in A verifying the contradictory (not(a <_A→B x) and a <_A→B x) or (x <_B→A a and not(x <_B→A a)).
  
• Transitivity (x ≥_AUB y and y ≥_AUB z → x ≥_AUB z):
  
  1. x, y, z in A: from the properties of <_A.
  2. x, y in A, z in B: from property 2.
  3. x in A, y in B, z in A: If x <_A z then not(z <_A x), which along with the hypothesis not(x <_A→B y) implies by property 2 that not(z <_A→B y), in contradiction with not(y <_B→A z) by property 1.
     
  4. x in A, y, z in B: if x <_A→B z, we would have by the hypothesis not(y <_B z) and the definition of <_B that x <_A→B y, in contradiction with the hypothesis not(x <_A→B y).
     
  5. x in B, y, z in A: from property 3.
  6. x in B, y in A, z in B: for any a in A, if not(a <_A y) then by property 2 not(a <_A→B z); and if not(y <_A a) we have by property 3 that not(x <_B→A a). So, the conditions for x <_B z are never satisfied.
  7. x, y in B, z in A: if x <_B→A z then by the hypothesis not(y <_B z) and the definition of <_B we would have the contradictory x <_B y.
  8. x, y, z in B: for any a in A, if not(a <_A→B x) then not(a <_A→B y) and thus not(a <_A→B z); whereas if x <_B→A a then y <_B→A a and hence z <_B→A a; so, it is not the case that x <_B z.
     
• Comparability (x ≥_AUB y or y ≥_AUB x):
  
  1. x, y in A: from the properties of <_A.
  2. x in A, y in B: from property 1.
  3. x in B, y in A: from property 1.
  4. x, y in B: if x <_B y then there exists some a in A such either not(a <_A→B x) and a <_A→B y, which implies not(a <_A→B x) and not(y <_B→A a); or else x <_B→A a and not(y <_B→A a), which also implies not(a <_A→B x) and not(y <_B→A a). Thus in either case y≥_AUB a ≥_AUB x, and by the transitivity of ≥_AUB, it follows that x ≥_AUB y.
     

Swos are important in C++ because sorting algorithms take comparison objects with swo semantics. The swo extension concept that we have developed is related to the notion of partitioning introduced by the C++ standard to describe binary search algorithms, as we will see in a later entry.

Societal usefulness of truth

Harry G. Frankfurt's much talked about On Truth purports that truth, i.e. the knowledge of true statements, is crucial to the development of advanced societies, and in defense of this view it summons the importance of acquiring true statements to the practice of engineering and medical science. In this section, Frankfurt makes in my opinion a bad exposition of the case because he implies that failure in a engineering or medical endeavour is always due to the acquisition of false statements (like results of field measures or medical tests), thus equating mispractice with falsehood.

Actually, the good practice of an empirical discipline depends on two sets of entities: field data and scientifical theories. A theory provides the justification for a given course of action based on the provided field data, but such theory is certainly not true (in the sense that it reflects a fact of the world or a Wittgensteinian "state of affairs") nor need it be. The quality of a scientifical theory is a delicate matter involving accuracy, causality, falsifiability and even politics, so it cannot be further from the layman concept of truth as a description of facts. So, from the two types of tools an empirical discpline resorts to, data and theories, only the first can be said to be dependent on truth.

A non-Euclidean characterization of convexity

A set X in a real vector space is convex if for every x, y in X the segment xy = {λx + (1−λ)y : 0 ≤ λ ≤ 1} is included in X. There are ways to extend the concept of convexity from vector spaces to metric spaces based on the translation of the "segment" concept: for instance, a set X in some suitable metric spaces is geodesically convex if for any pair of points x, y in X the geodesic between x and y is also in X. We explore an alternate extension of the concept of convexity that does not involve any kind of segment construct. The following considerations motivate the definition.

Consider some set X in Rⁿ (say R² for simplicity of display) composed of several irregular components. Imagine now that this set X is made of some radioactive material so that it creates a radiation wavefront propagating from X outwards:

If seen from a sufficiently long distance, the radiation wavefront is indistinguishable from that of a convex set Y with the same exterior shape as X:

So, the convex hull of X (or something very similar to it, as we will see later) can be reconstructed from its radiation wavefront at some distance r by retropropagating the wavefront towards X. Let us see a graphical example where X consists of three points and the wavefront w is considered at a distance r larger than the diameter of X:

Retropropagating w is equivalent to considering the wavefront at distance r generated by the exterior of w:

The resulting shape includes X and approximates the convex hull of X (in this case, the triangle with vertices in X) as r grows. So, we have a characterization of convexity resorting only to our wavefront construction, which can be formalized by means of metric space balls:

Definition. Let S be some metric space and X a set of points in S. The wavefront hull of X, H_wave(X), is defined as

H_wave(X) = U_r≥0B_r(B_r(X) \ S) \ S,

where B_r(A) is defined as the union of all closed balls of radius r centered at points in A.

Theorem. For any X in Rⁿ

H_wave(X) = X U int(H_convex(X)),

where int(A) denotes the interior set of A and H_convex(X) is the convex hull of X.

Corollary. cl(H_convex(X)) = ∩_r>0H_wave(B_r(X)), where cl(A) denotes the topological closure of A.

We will prove the theorem and corollary in a later entry.

Idle cartels

A cartel is an explicit and secretive agreement between rival companies in an oligopolistic market to take joint action so as to reduce effective competition and thus increase each firm's profit margins. Most countries enact competition laws that forbid the formation of cartels. But there are forms of market inefficiencies that can be brought about by the absence of agreement between competitors.

Numerical portability is the ability for a telephone subscriber to switch provider while retaining the line number; this is a very desirable feature, specially in the case of mobile telephony, and it definitely increases the global market utility. The problem is that in order to enjoy numerical portability between operators A and B, both A and B must have a portability agreement and add some costly functionality to their network cores. Therefore, there is no use in only one operator implementing portability, whereas if both operators provide it none will obtain a direct gain: churn would increase, which in principle favors competitive firms, but reducing competition is what cartels are all about. So, inaction here can be seen as a form of "idle cartel".

An idle cartel is not an actual cartel, since it happens without any explicit communication between firms. Even so, some regulation must be introduced by the government so as to avoid formation of idle cartels. Not that the free market's invisible hand is doing a fine job here.

A Steiner tree related theorem

This entry justifies some of the assumptions behind the algorithm devised at the prior entry "Within 50 km, revisited".

Let C be a finite set of 2D points called cities, and r > 0. The r-coverage problem for C, abbreviated Cov(C,r), consists of finding a set of nodes N and an associated tree T spanning those nodes with the following properties:

• For every c in C there is some n in N such that dist(c,n) ≤ r (coverage property).
  
• The length of T is minimum.
  

It is easy to see that for any solution (N,T) to Cov(C,r) the tree T is the Steiner tree of N, ST(N), so we need only concentrate on finding the set of nodes N. We now prove that, under certain conditions, we can restrict our search for solutions to Cov(C,r) to nodes lying in the r-circles centered at the cities of C.

Definition. A set of cities C is r-separable if for any c in C there is some c' in C such that dist(c,c') ≥ 2r.

Theorem. Let us index the set of cities C as c₁,...,c_m, and let M = {{n₁,...,n_m} : n_i in D(c_i,r)}, where D(c_i,r) is the circle of radius r centered at the point c_i. If C is r-separable, there is a solution (D,ST(D)) to Cov(C,r) such that D belongs to M.

Lemma. Let A be a set of points and B a set of points lying in ST(A). Then, length(ST(B)) ≤ length(ST(A)). Proof. Obviously ST(A+B) = ST(A). Now, from the properties of Steiner trees it follows that if X is a subset oy Y, length(ST(X)) ≤ length(ST(Y)), and as B is a subset of A+B we have length(ST(B)) ≤ length(ST(A+B)) = length(ST(A)).

Proof of theorem. Let (N,ST(N)) be a solution to Cov(C,r). From the r-separability of C, ST(N) must intersect each circle D(c_i,r) at some point d_i; now, if we take (D,ST(D)), where D = {d₁,..,d_m}, it is easy to see that

• D satisfies the coverage property,
  
• by our prior lemma, length(ST(D)) cannot be greater than length(ST(N)),
  

so (D,ST(D)) is a solution to Cov(C,r).

A paradoxical three-person game: out of paradox and back into it

The numerical solution to the N-option Mediocrity game disproves in a sense the validity of a kind of circular reasoning that we posed in our presentation of the game:

"I must choose among 1,4,...,3N-2. Clearly 1 can never be in the middle, so I discard it. Player B, however, knows I won't play 1, so she won't choose 2, and thus player C, who can also deduce this, won't play 3. Hence 4 is not an option for me either, and this implies B won't play 5,..."

This was the argument of A; B and C can reason in a similar fashion so as to come to the joint conclusion that no valid choice can be made. How come our numerical solution points to the existence of valid strategies after all?

When N is even, we have proved that B cannot win, so any choice is as good as any other for her. This invalidates the reasoning made by A that goes "Player B, however, knows I won't play 1, so she won't choose 2..." This "wavefront" of position discarding advances only as long as the three players assume there is some strategy with non-null payoff.

When N is odd, the alluded wavefront somehow ripples back when the central positions are reached. Consider the game for N=3:

1	2	3	4	5	6	7	8	9
A	B	C	A	B	C	A	B	C

Let's unfold a plausible, if admittedly not an ineluctable, reasoning for B:

"A cannot choose the losing position 1, and similarly C cannot choose 9, so this discards my positions at 2 and 8 as valid moves. Now, my having discarded 2 and 8 causes A and C to drop 7 and 3, respectively, and by an iteration of the argument 4 and 6 must also go. But now A and C are without any valid choice to make: going one step back results in A choosing 4 and C playing 6, which is a sure loosing strategy for them; one further step back, my opponents can come up with positions beating my choosing 5."

Again, the circularity breaks down once the chain of reasoning leads to a dead end.

N odd, N ≥ 3: implicit coalitions and self-cheating. Let's examine the optimum strategies for A and C when N=3 (the situation is equivalent for other odd values of N greater than 3): Although the rules we established for the game forbid coalitions, an implicit one is formed between A and C so as to erode B's central position at 5. The possible outcomes of the game are then (bolds mark the winner):

A←4,B←5,C←3
A←4,B←5,C←6
A←7,B←5,C←3
A←7,B←5,C←6

so that A and C manage to take a payoff of 1/4 each away from B. The implicit coalition emerges from the fact that A and C are in entirely symmetrical positions and both are perfectly rational, and know the same is true of the other: this allows them to conclude that their strategies must coincide (doing the appropriate reversions). In a way, symmetry makes up for the lack of communication between players.

But, upon tossing the coin to decide whether to play 4 or 7, A could have a final moment of reflection: "Wait, if I don't choose at random and go instead always for 4, my chances of winning rise from 25% to 33%!" What's wrong with defeating at this point? Well, if C does the analogous reasoning and plays 6 unconditionally, then the sure winner is B --a classical Prisoner's dilemma here between A and C. The twist is that we assumed that the optimum strategies for A and C must be symmetrical, so A's defection is tantamount to self-cheating. I don't know whether this conflict is amenable to a rational analysis after all. Maybe Hofstadter's concept of superrationality could be invoked here to escape the riddle, although some, I among them, may be inclined to regard superrationality as a mere sleight of hand.