text:
# The Phillips Curve, Again

The Phillips Curve is back. In saying so, I do not mean to imply that being “back” refers to a sudden reappearance of a stable empirical relationship between unemployment (or the output gap) and inflation. The Phillips Curve is back in the same way that conspiracy theories about the assassination of JFK are back after the recent release of government documents. In other words, the Phillips Curve is something that people desperately want to believe in, despite the lack of evidence.

The Phillips Curve is all the rage among central bankers. Since the Federal Reserve embarked on quantitative easing, they have been ensuring the public that QE would not be inflationary because of the slack in the economy. Until labor market conditions tighten, there would be little threat of inflation. Then, as the labor market tightened, the Federal Reserve warned that they might have to start raising interest rates to prevent these tightening conditions from creating inflation.

What is remarkable about this period is that the Federal Reserve has undershot its target rate of inflation throughout this entire period — and continues to do so today. So what does this tell us about the Phillips Curve and what can we learn about monetary policy?

If one looks at the data on unemployment and inflation (or even the output gap and inflation), you could more easily draw Orion the Hunter as you could a stable Phillips Curve. Fear not, sophisticated advocates of the Phillips Curve will say. This is simply the Lucas Critique at play here. If a Phillips Curve exists, and if the central bank tries to exploit it, then it will not be evident in the data. In fact, if you take a really basic 3-equation-version of the New Keynesian model, there is a New Keynesian Phillips Curve in the model. However, when you solve for the equilibrium conditions, you find that inflation is a function of demand shocks, technology shocks, and unexpected changes in interest rates. The output gap doesn’t appear in the solution. But fear not, this simply means that monetary policy is working properly. The Phillips Curve is apparently like the observer effect in quantum mechanics in that when we try to observe the Phillips Curve, we change the actual result (this is a joke, please do not leave comments about why I’ve misunderstood the observer effect).

However, I would like to submit that even this interpretation is problematic for thinking about monetary policy and defending the Phillips Curve. In the New Keynesian model, we get an equation that looks like this:

$\pi_t = \beta E_t \pi_{t+1} + \kappa y_t$

where $\pi$ is the rate of inflation, $y_t$ is the output gap, and $\kappa$ and $\beta$ are parameters. This equation is an equilibrium condition of the model. Since it is an equilibrium condition, it always holds. This equilibrium condition can be derived by (1) having a monopolistically competitive firm solve a profit-maximization problem with a Rotemberg-esque quadratic adjustment cost associated with prices, (2) solving for a symmetric equilibrium, and (3) log-linearizing around the steady state. So this is an equilibrium condition for the aggregate economy. When you look at this equation, you would think that you can use this equation for some intuition about the evolution of inflation. To demonstrate how silly it would be to do so, let’s assume that people in the economy are sufficiently patient that we can re-write this equation as:

$\pi_t = E_t \pi_{t+1} + \kappa y_t$

So you look at this equilibrium condition and you get a very New Keynesian interpretation of the world. It looks as though inflation is explained by changes in expected inflation and changes in the output gap. However, this interpretation is wrong. This equation is an equilibrium relationship. Thus, I could just as easily re-write this equation as

$y_t = \frac{1}{\kappa} (\pi_t - E_t \pi_{t+1})$

Hmm. Now we have something that looks like an expectations augmented Phillips Curve with the direction of causation moving in the opposite direction. Now, it looks as though unexpected changes in inflation are causing changes in the output gap.

So what is a central bank to do?

Actually, using this equation alone, we can’t say anything at all! This equation is just an equilibrium relationship. Without knowing anything else about the economy, this tells us nothing. We have one equilibrium equation with two unknowns. In addition, we have a rational expectation about inflation, which implies that the expectation is model-consistent. In order to know what a model consistent expectation is, we need to have a model from which we can form expectations. In other words, this equation tells us absolutely nothing in isolation from a bigger model.

For example, suppose that we are in a world with the gold standard. Let $p_t$ be the log of the price level. A reasonable assumption would be that $p_t$ follows a random walk:

$p_t = p_{t-1} + e_t$

or

$\pi_t = e_t$

Combining this with our Phillips Curve would give us

$y_t = \frac{1}{\kappa} \pi_t = \frac{1}{\kappa} e_t$

So output and inflation are driven by shocks to the price level. There is no exploitable relationship between inflation and the output gap, despite the fact that (a) regressing the output gap on inflation would yield a positive coefficient, and (b) the model features a New Keynesian Phillips Curve. This is important because the best evidence that we have when it comes to the Phillips Curve is from the gold standard era.

In addition, if the quantity theory holds, then the rate of inflation and the expected rate of inflation would be determined by the path of money supply. Output would then adjust to fit the equilibrium condition that looks like a Phillips Curve. This was the view of Fisher and Friedman, for example.

What all of this means is that even given the fact that the New Keynesian model features an equation that resembles the Phillips curve, this does not imply that there is some predictive power that comes from thinking about this equation in isolation. In addition, it certainly does not imply that changes in the output gap cause changes in the rate of inflation. There is no direction of causation implied by this one equilibrium condition.

### 10 responses to “The Phillips Curve, Again”

1. Iskander

Great post! I’ve seen nothing recently as annoying as the claim that labour market tightness causes inflation. David Laidler has an essay in “Monetarist Perspectives” that suggests that there have been two visions of the Phillips curve, the Fisherian and the Phelpsian.

2. Pete Bias

You know what Scott Sumner is always bothered by: “reasoning from a price (level rate of growth) change”. For instance, whip out a dynamic equation of exchange and suddenly inflation and gdp growth are negatively related (with money rate of growth constant).
Counting on Phillips curves to do your work is dangerous; and arguing that “it was Friedman’s thermostat!” to defend the lack of empirical support allows for you to claim anything. Popper wouldn’t approve.
The Phillips relation might be right, but I want to be shown. Dig and find this relationship if it’s truly there.

3. Ilya

Josh,
Are there any papers written by others whom you think have the “correct alternative” to the Phillips curve thinking?

4. You’re hitting on a more general point, but I think your example is a great one to focus on.

The more general point: suppose you are interested in how *any* two economic variables are connected. To learn about them, you cannot explicitly model both variables and derive a relationship between them. That is, you cannot have both variables be equilibrium objects. Instead, one variable must always be exogenous, which is just an exotic term for “not modeled”. This has always been one of the strangest things to me about modeling and empirical work. My intuition is still if I am interested in some variables, I should explicitly model how they are jointly determined. It is the Walrasian sin.

All economists know this point in the simplest example: price and quantity. I can’t learn about their empirical connection through a model of supply and demand where both variables are jointly pinned down. That is, supply and demand cannot tell me how price affects quantity or quantity affects price. Instead, I need to model just one side, say demand, and exogenously feed-in price fluctuations to find quantity fluctuations. There I can derive a negative relationship between price and quantity. But obviously, that negative relationship is not true for the whole market. I certainly would be a fool to plot price and quantity to back out an equation of their connection.

Again, this obvious point about supply and demand is unintuitive to me when we start talking about more general relationships.

5. Nice post, things explained in details. Thank You.

6. J. Preston Tarkington

Reblogged this on Something Interesting: and commented:
Originally posted by The Everyday Economist:

7. Hey Josh, sort of unrelated question. What are your thoughts on Hayek’s Ricardo Effect? Much appreciated.

8. What i don’t realize is if truth be told how you are not actually much more neatly-appreciated
than you may be now. You are very intelligent. You know
therefore significantly in relation to this matter, made me in my
opinion consider it from numerous various angles. Its like women and men don’t seem
to be fascinated unless it’s something to do with Girl gaga!
Your personal stuffs great. At all times maintain it up!

9. David Harold Chester

Before we begin to make conclusions on what is a good policy we badly need to better understand how our social system of macroeconomics works. It is not as simple as the formulae given above and it actually involves at least 19 variables as an absolute minimum, see SSRN 2865571 “Einstein’s Criterion Applied to Logical Macroeconomics Modeling”. To see the associated diagram or map of the model, please go this reference which is easy to find on the internet.

In that short paper there is a reference to my 310 book which will provide the means for finding out about the effect of any externally applied displacement from an assumed state of equilibrium, or when a change is deliberately introduced.

Having reduced the “Big Picture” to its most simple yet complete terms, it is not easy to determine how it will react to a change, but with this tool it is at last possible in a formal and completely logical procedure to find out what MUST happen. Write to me for a free 310 page e-copy of “Consequential Macroeconomics” , and at last discover that our subject is an almost exact science, that is relatively simple to follow, compared to the confusion currently otherwise available.


text:
## On linear stochastic flows

### Beniamin Goldys and Szymon Peszat

#### Abstract

We study the existence of the stochastic flow associated to a linear stochastic evolution equation $\mathrm{d} X= AX\,\mathrm{d} t +\sum_{k} B_k X\,\mathrm{d} W_k,$ on a Hilbert space. Our first result covers the case where $$A$$ is the generator of a $$C_0$$-semigroup, and $$(B_k)$$ is a sequence of bounded linear operators such that $$\sum_k\|B_k\|<+\infty$$. We also provide sufficient conditions for the existence of stochastic flows in the Schatten classes beyond the space of Hilbert-Schmidt operators. Some new results and examples concerning the so-called commutative case are presented as well.

Keywords: stochastic flow, stochastic equation with multiplicative noise, Schatten class.

: Primary 60H15; secondary 60G15, 60G60.

This paper is available as a pdf (420kB) file.

 Wednesday, May 5, 2021

format: plain


text:
Isoptic point and Simson line of a quadrilateral

# The perpendicular bisectors construction, the isoptic point and the Simson line of a quadrilateral

## 1. Introduction

The perpendicular bisector construction that we investigate in this paper arises very naturally in an attempt to find a replacement for a circumcenter in the case of a noncyclic quadrilateral . Indeed, while there is no circle going through all four vertices, for every triple of vertices there is a unique circle (called the triad circle) passing through them. The centers of these four triad circles can be taken as the vertices of a new quadrilateral, and the process can be iterated to obtain a sequence of noncyclic quadrilaterals:

To reverse the iterative process, one finds isogonal conjugates of each of the vertices with respect to the triangle formed by the remaining vertices of the quadrilateral.

It turns out that all odd generation quadrilaterals are similar, and all even generation quadrilaterals are similar. Moreover, there is a point that serves as the center of spiral similarity for any pair of odd generation quadrilaterals as well as for any pair of even generation quadrilaterals. The angle of rotation is or depending on whether the quadrilateral is concave or convex, and the ratio of similarity is a constant that is negative for convex noncyclic quadrilaterals, zero for cyclic quadrilaterals, and for concave quadrilaterals. If , the same special point turns out to be the limit point for the iterative process or for the reverse process.

The main goal of this paper is to prove the following

###### Theorem.

For each quadrilateral there is a unique point that has any (and, therefore, all) of the following properties:

1. is the center of the spiral similarity for any two odd (even) generation quadrilaterals in the iterative process;

2. Depending on the value of the ratio of similarity in the iterative process, there are the following possibilities:

1. If , the quadrilaterals in the iterated perpendicular bisectors construction converge to ;

2. If , the iterative process is periodic (with period or ); is the common center of rotations for any two odd (even) generation quadrilaterals;

3. If , the quadrilaterals in the reverse iterative process (obtained by isogonal conjugation) converge to ;

3. is the common point of the six circles of similitude for any pair of triad circles , , where , , , .

4. (isoptic property) Each of the triad circles is visible from at the same angle.

5. (generalization of circumcenter) The (directed) angle subtended by any of the quadrilateral’s sides at equals to the sum of the angles subtended by the same side at the two remaining vertices.

6. (isodynamic property) The distance from to any vertex is inversely proportional to the radius of the triad circle determined by the remaining three vertices.

7. is obtained by inversion of any of the vertices of the original quadrilateral in the corresponding triad-circle of the second generation:

 W=Invo(2)1(A)=Invo(2)2(B)=Invo(2)3(C)=Invo(2)4(D),

where , , , .

8. is obtained by composition of isogonal conjugation of a vertex in the triangle formed by the remaining vertices and inversion in the circumcircle of that triangle.

9. is the center of spiral similarity for any pair of triad circles (of possibly different generations). That is, for all .

10. The pedal quadrilateral of is a (nondegenerate) parallelogram. Moreover, its angles equal to the angles of the Varignon parallelogram.

Many of these properties of were known earlier. In particular, several authors (G.T. Bennett in an unpublished work, De Majo [2], H.V. Mallison [3]) have considered a point that is defined as the common center of spiral similarities. Once the existence of such a point is established, it is easy to conclude that all the triad circles are viewed from this point under the same angle (this is the so-called isoptic property). Since it seems that the oldest reference to the point with such an isoptic property is to an unpublished work of G.T. Bennett given by H.F. Baker [1] in his “Principles of Geometry” (vol. 4), in 1925, we propose to call the center of spiral similarities in the iterative process Bennett’s isoptic point.

C.F. Parry and M.S. Longuet-Higgins [4] showed the existence of a point with property 7 using elementary geometry.

Mallison [3] defined using property 3 and credited T. McHugh for observing that this implies property 5.

Several authors, including Wood [5] and De Majo [2], have looked at the properties of the isoptic point from the point of view of the unique rectangular hyperbola going through the vertices of the quadrilateral, and studied its properties related to cubics. For example, P.W. Wood [5] considered the diameters of the rectangular hyperbola that go through . Denoting by the other endpoints of the diameters, he showed that the isogonal conjugates of these points in triangles , ,, coincide. Starting from this, he proved properties 4 and 7 of the theorem. He also mentions the reversal of the iterative process using isogonal conjugation (Also found in [5], [6], [15]). Another interesting property mentioned by Wood is that is the Fregier point of the center of the rectangular hyperbola for the conic , where O is the center of the rectangular hyperbola.

De Majo [2] uses the property that inversion in a point on the circle of similitude of two circles transforms the original circles into a pair of circles whose radii are inversely proportional to those of the original circles to show that that there is a common point of intersection of all circles of similitude. He describes the iterative process and states property 1, as well as several other properties of (including 8). Most statements are given without proofs.

Scimemi [6] describes a Möbius transformation that characterizes : there exists a line going through and a circle centered at such that the product of the reflection in the line with the inversion in the circle maps each vertex of the first generation into a vertex of the second generation.

The fact that the third generation quadrilateral is similar to the original quadrilateral and the expression for the ratio of similarity has appeared in the form of a problem by V.V. Prasolov in [7, 8]. Independently, the same question was formulated by J. Langr [9] , and the expression for the ratio (under certain conditions) was obtained by D. Bennett [10] (apparently, no relation to G.T. Bennett mentioned above), and J. King [11]. A paper by G.C. Shepard [12] found an expression for the ratio as well. (See [13] for a discussion of these works).

Properties 9 and 10 appear to be new.

For the convenience of the reader, we give a complete and self-contained exposition of all the properties in the Theorem above, as well as proofs of several related statements.

In addition to investigating properties of , we show that there is a unique point for which the feet of the perpendiculars to the sides lie on a straight line. In analogy with the case of a triangle, we call this line the Simson line of a quadrilateral and the point — the Simson point. The existence of such a point is stated in [16] where it is obtained as the intersection of the Miquel circles of the complete quadrilateral.

Finally, we introduce a version of isogonal conjugation for a quadrilateral and show that the isogonal conjugate of is a parallelogram, and that of the Simson point is a degenerate quadrilateral whose vertices are at infinity, in analogy with the case of the points on the circumcircle of a triangle.

## 2. The iterative process

Let be a quadrilateral. If is cyclic, the center of the circumcircle can be found as the intersection of the perpendicular bisectors to the sides of the quadrilateral.

Assume that is a noncyclic quadrilateral1. Is there a point that, in some sense, plays the role of the circumcenter? Let be the quadrilateral formed by the intersections of the perpendicular bisectors to the sides of . The vertices of the new quadrilateral are the circumcenters of the triad-triangles , , and formed by vertices of the original quadrilateral taken three at a time.

Iterating this process (i.e., constructing the vertices of the next generation quadrilateral by intersecting the perpendicular bisectors to the sides of the current one), we obtain the successive generations, , and so on, see Figure 2.1.

The first thing we note about the iterative process is that it can be reversed using isogonal conjugation. Recall that given a triangle and a point , the isogonal conjugate of with respect to (denoted by ) is the point of intersection of the reflections of the lines , and in the angle bisectors of , and respectively. One of the basic properties of isogonal conjugation is that the isogonal conjugate of is the circumcenter of the triangle obtained by reflecting in the sides of (see, e.g., [15] for more details). This property immediately implies

###### Theorem 1.

The original quadrilateral can be reconstructed from the second generation quadrilateral using isogonal conjugation:

 A1=Iso△D2A2B2(C2),B1=Iso△A2B2C2(D2),C1=Iso△B2C2D2(A2),D1=Iso△C2D2A2(B2).

The following theorem describes the basic properties of the iterative process.

###### Theorem 2.

1. degenerates to a point if and only if is cyclic.

2. If is not cyclic, the corresponding angles of the first and second generation quadrilaterals are supplementary:

 ∠A1+∠A2=∠B1+∠B2=∠C1+∠C2=∠D1+∠D2=π.
3. If is not cyclic, all odd generation quadrilaterals are similar to each other and all the even generation quadrilaterals are similar to each other:

 Q(1)∼Q(3)∼Q(5)∼…, Q(2)∼Q(4)∼Q(6)∼….
4. All odd generation quadrilaterals are related to each other via spiral similarities with respect to a common center.

5. All even generation quadrilaterals are also related to each other via spiral similarities with respect to a common center.

6. The angle of rotation for each spiral similarity is (for a convex quadrilateral) or a (for a concave quadrilateral). The ratio of similarity is

 (2.1) r=14(cotα+cotγ)⋅(cotβ+cotδ),

where , , and are the angles of .

7. The center of spiral similarities is the same for both the odd and the even generations.

###### Proof.

The first and second statements follow immediately from the definition of the iterative process. To show that all odd generation quadrilaterals are similar to each other and all even generation quadrilaterals similar to each other, it is enough to notice that both the corresponding sides and the corresponding diagonals of all odd (even) generation quadrilaterals are pairwise parallel.

Let be the center of spiral similarity taking into . Similarly, let be the center of spiral similarity taking into . Denote the midpoints of segments and by and . (See fig. 2.2). To show that and coincide, notice that . Since the corresponding sides of these triangles are parallel, they are related by a spiral similarity. Since and , it follows that . Let now be the center of spiral similarity that takes into . By the same reasoning, , which implies that . Continuing by induction, we conclude that the center of spiral similarity for any pair of odd generation quadrilaterals coincides with that for any pair of even generation quadrilaterals. We denote this point by . ∎

Properties (2) and (3) of the theorem above imply the following

###### Corollary 3.

The even and odd generation quadrilaterals are similar to each other if and only if is a trapezoid.

The ratio of similarity takes values in and characterizes the shape of in the following way:

1. if and only if is convex. Moreover, if and only if is cyclic.

2. if and only if is concave. Moreover, if and only if is orthocentric (that is, each of the vertices is the orthocenter of the triangle formed by the remaining three vertices. Alternatively, an orthocentric quadrilateral is characterized by being a concave quadrilateral for which the two opposite acute angles are equal).

For convex quadrilaterals, can be viewed as a measure of how noncyclic the original quadrilateral is. Recall that since the opposite angles of a cyclic quadrilateral add up to , the difference

 (2.2) |(α+γ)−π|=|(β+δ)−π|

can be taken as the simplest measure of noncyclicity. This measure, however, treats two quadrilaterals with equal sums of opposite angles as equally noncyclic. The ratio provides a refined measure of noncyclicity. For example, for a fixed sum of opposite angles, , , where , the convex quadrilateral with the smallest is the parallelogram with , .

Similarly, for concave quadrilaterals, measures how different the quadrilateral is from being orthocentric.

Since the angles between diagonals are the same for all generations, it follows that the ratio is the same for all pairs of consecutive generations:

 Area(Q(n))Area(Q(n−1))=|r|.

Assuming the quadrilateral is noncyclic, there are the following three possibilities:

1. When (which can only happen for convex quadrilaterals), the quadrilaterals in the iterative process converge to .

2. When , the quadrilaterals in the inverse iterative process converge to .

3. When , all the quadrilaterals have the same area. The iterative process is periodic with period for all quadrilaterals with , except for the following two special cases. If is either a parallelogram with angle (so that ) or forms an orthocentric system (so that ), we have , , and the iterative process is periodic with period .

By setting in formula (2.1), we obtain the familiar relations between the sides and diagonals of a cyclic quadrilateral :

Since the vertices of the next generation depend only on the vertices of the previous one (but not on the way the vertices are connected), one can see that and for the (self-intersecting) quadrilaterals and coincide with those for . This observation allows us to prove the following

###### Corollary 4.

The angles between the sides and the diagonals of a quadrilateral satisfy the following identities:

 (cotα+cotγ)⋅(cotβ+cotδ) = (cotα1−cotβ2)⋅(cotδ2−cotγ1), (cotα+cotγ)⋅(cotβ+cotδ) = (cotδ1−cotα2)⋅(cotβ1−cotγ2)

where , are the directed angles formed between sides and diagonals of a quadrilateral (see Figure 2.3).

###### Proof.

Since the (directed) angles of are and the directed angles of are , the identities follow from formula (2.1) for the ratio of similarity. ∎

## 3. Properties of the Center of Spiral Similarity

We will show that , defined as the limit point of the iterated perpendicular bisectors construction in the case that (or of its reverse in the case that ), is the common center of all spiral similarities taking any of the triad circles into another triad circle in the iterative process.

First, we will prove that any of the triad circles of the first generation quadrilateral can be taken into another triad circle of the first generation by a spiral similarity centered at (Theorem 8). This result allows us to view as a generalization of the circumcenter for a noncyclic quadrilateral (Corollary 9 and Corollary 12), to prove its isoptic (Theorem 10), isodynamic (Corollary 13) and inversive (Theorem 14) properties, as well as to establish some other results. We then prove several statements that allow us to conclude (see Theorem 23) that serves as the center of spiral similarities for any pair of triad circles of any two generations.

Several objects associated to a configuration of two circles on the plane will play a major role in establishing properties of . We will start by recalling the definitions and basic constructions related to these objects.

### 3.1. Preliminaries: circle of similitude, mid-circles and the radical axis of two circles.

Let and be two (intersecting2) circles on the plane with centers and and radii and respectively. Let and be the points of intersection of the two circles. There are several geometric objects associated to this configuration (see Figure 3.1):

1. The circle of similitude is the set of points on the plane such that the ratio of their distances to the centers of the circles is equal to the ratio of the radii of the circles:

 |PO1||PO2|=R1R2.

In other words, is the Apollonian circle determined by points , and ratio .

2. The radical axis can be defined as the line through the points of intersection.

3. The two mid-circles (sometimes also called the circles of antisimilitude) and are the circles that invert into , and vice versa:

 InvMCi(o1,o2)(o1)=o2,i=1,2.

Here are several important properties of these objects (see [16] and [17] for more details):

1. is the locus of centers of spiral similarities taking into . For any , there is a spiral similarity centered at that takes into . The ratio of similarity is and the angle of rotation is .

2. Inversion with respect to takes centers of and into each other:

 InvCS(o1,o2)(O1)=O2.
3. Inversion with respect to any of the mid-circles exchanges the circle of similitude and the radical axis:

 InvMCi(o1,o2)(CS(o1,o2))=RA(o1,o2),i=1,2.
4. The radical axis is the locus of centers of all circles that are orthogonal to both and .

5. For any , inversion in a circle centered at takes the circle of similitude of the original circles into the radical axis of the images, and the radical axis of the original circles into the circle of similitude of the images:

 CS(o1,o2)′=RA(o′1,o′2),
 RA(o1,o2)′=CS(o′1,o′2).

Here denotes the image of an object under the inversion in a circle centered at .

6. Let be points on the circles respectively. Then

 (3.1) ∠AMB=∠AKB+∠ALB,

where the angles are taken in the sense of directed angles.

7. Let be a chord of a circle and be a chord of a circle . Then are on a circle if and only if

It is also useful to recall the construction of the center of a spiral similarity given the images of two points. Suppose that and are transformed into and respectively. Let . The center of the spiral similarity can be found as the intersection , where here and below stands for the circle going through .

We will call point in this construction the joint point associated to two given points and their images under spiral similarity.

There is another spiral similarity associated to the same configuration of points. Let be the joint point for the spiral similarity taking and into and respectively. A simple geometric argument shows that the center of this spiral similarity, determined as the intersection of the circles , coincides with . We will call such a pair of spiral similarities centered at the same point associated spiral similarities.

Let be the spiral similarity centered at that takes into . The following Lemma will be useful when studying properties of the limit point of the iterative process (or of its inverse):

###### Lemma 5.

Let and be two circles centered at and respectively and intersecting at points and . Let be points on the circle of similitude such that and are symmetric to each other with respect to the line of centers, . Then the joint points corresponding to taking , by and taking , by coincide. The common joint point lies on .

###### Proof.

Perform inversion in the mid-circle. The image of is the radical axis (i.e., the line through and ). The images of and lie on the line and are symmetric with respect to . Similarly, the images of and are symmetric with respect to and lie on the line of centers. By abuse of notation, we will denote the image of a point under inversion in the mid-circle by the same letter.

The lemma is equivalent to the statement that lies on the circle . To show this, note that since and W lie on a circle, we have Since and it follows that which implies that lie on a circle. After inverting back in the mid-circle, we obtain the result of the lemma. ∎

Notice that the lemma is equivalent to the statement that

 RR1,2∩SS2,1=(WRO1)∩(WSO2)∈O1O2.

### 3.2. W as the center of spiral similarities for triad circles of Q(1).

Denote by and the triad circles , , and respectively.3 For triad circles in other generations, we add an upper index indicating the generation. For example, denotes the first triad-circle in the rd generation quadrilateral, i.e., circle . Let and be the triad triangles , , and respectively.

Consider two of the triad circles of the first generation, and , . The set of all possible centers of spiral similarity taking into is their circle of similitude . If is a nondegenerate quadrilateral, it can be shown that and intersect at two points (i.e. are not tangent). Let be the other point of intersection of and .4

Let be the spiral similarity centered at that takes into for any .

###### Lemma 6.

Spiral similarities have the following properties:

1. .

2. .

###### Proof.

Assume that . Let be the joint point of the spiral similarity (centered at ) taking into and into . Since points lie on a circle (see Lemma 5), it follows that . Thus, is a diameter of Since is centered at , the circles and are tangent at . It is easy to see that the converse is also true: if and are tangent at , then .

Since lie on a circle, it follows that . Since and under , . This implies that the circles and are tangent at . It is easy to see that is tangent to if and only if is tangent to .

Similarly to the above, let be the joint point of the spiral similarity centered at and taking into . Then . Similarly to the argument above, is tangent to if and only if is tangent to . This is equivalent to .

The second statement follows since . (Here and below the compositions of transformations are read right to left). ∎

Notice that circles and have two common vertices, and . The next Lemma shows that takes (i.e., the third vertex on ) to (the third vertex on ). This property is very important for showing that any triad circle from the first generation can be transformed into another triad circle from the first generation by a spiral similarity centered at . Similar properties hold for and . Namely, we have

, , .

###### Proof.

Lemma 6 shows that implies . Assume that . To find the image of under , represent the latter as the composition . First, , where is as in Lemma 6, see Figure 3.3. For brevity, let . (The indices refer to the fact that is the image of under spiral similarity taking into ).

Now we construct . By Lemma 5, , where is as in Lemma 6. Applying Lemma 5 to the circle , we conclude that it passes through . Since by assumption , it follows that . Thus, . The other statements in the Lemma can be shown in a similar way. ∎

The last Lemma allows us to show that lies on all of the circles of similitude .

for all .

###### Proof.

By definition, . We will show that for any .

Recall that . Let be the second point in the intersection , so that . By Lemma 7, . Since , it follows that , which implies that . Therefore, is the common point for all the circles of similitude , . ∎

### 3.3. Properties of W

The angle property (3.1) of the circle of similitude implies

###### Corollary 9.

The angles subtended by the quadrilateral’s sides at are as follows (see Figure 3.4):

 ∠AWB = ∠ACB+∠ADB, ∠BWC = ∠BAC+∠BDC, ∠CWD = ∠CAD+∠CBD, ∠DWA = ∠DBA+∠DCA.

This allows us to view as a replacement of the circumcenter in a certain sense: the angle relations above are generalizations of the relation between the angles in a cyclic quadrilateral with circumcenter . (Of course, in this special case, ).

Since for all , can be used as the center of spiral similarity taking any of the triad circles into another triad circle. This implies the following

###### Theorem 10.

(Isoptic property) All the triad circles subtend equal angles at

In particular, is inside of all of the triad circles in the case of a convex quadrilateral and outside of all of the triad circles in the case of a concave quadrilateral. (This was pointed out by Scimemi in [6]). If is inside of a triad circle, the isoptic angle equals to , where and are the points on the circle so that goes through and . (See Figure 3.5, where and are halves of the isoptic angle in and respectively). If is outside of a triad circle centered at and is the tangent line to the circle, so that is point of tangency, is half of the isoptic angle. Inverting in a triad circle of the second generation, we get that the triad circles are viewed at equal angles from the vertices opposite to their centers (see Figure 3.5).

Recall that the power of a point with respect to a circle centered at with radius is the square of the length of the tangent from to the circle, that is,

 h=|PO|2−R2.

The isoptic property implies the following

###### Corollary 11.

The powers of with respect to triad circles are proportional to the squares of the radii of the triad circles.

This property of the isoptic point was shown by Neville in [14] using tetracyclic coordinates and the Darboux-Frobenius identity.

Let be sides of the quadrilateral. For any , let be the foot of the perpendicular bisector of side on the opposite side. (E.g., is the intersection of the perpendicular bisector to the side and the side ). The following corollary follows from Lemma 7 and expresses as the point of intersection of several circles going through the vertices of the first and second generation quadrilaterals, as well as the intersections of the perpendicular bisectors of the original quadrilateral with the opposite sides (see Fig. 3.6).

###### Corollary 12.
 (3.2) W=(A1FbB2)∩(A1FcD2)∩(B1FcC2)∩(B1FdA2)∩(C1FdD2)∩(C1FaB2)∩(D1FaA2)∩(D1FbC2),

This property can be viewed as the generalization of the following property of the circumcenter of a triangle:

Given a triangle with sides opposite to vertices , let denote the feet of the perpendicular bisector to side on the side (or its extension), where . Then the circumcenter is the common point of three circles going through vertices and feet of the perpendicular bisectors in the following way:5 (3.3)

The similarity between (3.3) and (3.2) supports the analogy of the isoptic point with the circumcenter.

The last corollary provides a quick way of constructing . First, construct two vertices (e.g., and ) of the second generation by intersecting the perpendicular bisectors. Let be the intersection of the lines and . Then is obtained as the second point of intersection of the two circles and .

Recall the definition of isodynamic points of a triangle. Let be a triangle with sides opposite to the vertices . For each , where , consider the circle centered at and going through . The circle of similitude of two distinct circles and is the Apollonian circle with respect to points with ratio . It is easy to see that the three Apollonian circles intersect in two points, and , which are called the isodynamic points of the triangle.

Here are some properties of isodynamic points (see, e.g., [16], [17] for more details):

1. The distances from (and ) to the vertices are inversely proportional to the opposite side lengths:

 (3.4) |SA1|:|SA2|:|SA3|=1a1:1a2:1a3.

Equivalently,

 |SAi|:|SAj|=sinαj:sinαi,i≠j∈{1,2,3},

where is the angle in the triangle. The isodynamic points can be characterized as the points having this distance property. Note that since the radii of the circles used to define the circles of similitude are the sides, the last property means that distances from isodynamic points to the vertices are inversely proportional to the radii of the circles.

2. The pedal triangle of a point on the plane of is equilateral if and only if the point is one of the isodynamic points.

3. The triangle whose vertices are obtained by inversion of with respect to a circle centered at a point is equilateral if and only if is one of the isodynamic points of .

It turns out that has properties (Corollary 13, Theorem 29, Theorem 26) similar to properties 1–3 of .

###### Corollary 13.

(Isodynamic property of ) The distances from to the vertices of the quadrilateral are inversely proportional to the radii of the triad-circles going through the remaining three vertices:

 |WA1|:|WB1|:|WC1|:|WD1|=1R3:1R4:1R1:1R2,

where is the radius of the triad-circle . Equivalently, the ratios of the distances from to the vertices are as follows:

 |WA1|:|WB1| = |A1C1|sinγ:|B1D1|sinδ, |WA1|:|WC1| = sinγ:sinα, |WB1|:|WD1| = sinδ:sinβ.

From analysis of similar triangles in the iterative process, it is easy to see that the limit point of the process satisfies the above distance relations. Therefore, (defined at the beginning of this section as the second point of intersection of and ) is the limit point of the iterative process.

One more property expresses as the image of a vertex of the first generation under the inversion in a triad circle of the second generation. Namely, we have the following

###### Theorem 14.

(Inversive property of W)

 (3.5) W=Invo(2)1(A1)=Invo(2)2(B1)=Invo(2)3(C1)=Invo(2)4(D1).
###### Proof.

To prove the first equality, perform inversion in a circle centered at . The image of a point under the inversion will be denoted by the same letter with a prime. The images of the circles of similitude , and are the perpendicular bisectors of the segments , and respectively. By Theorem


text:
# GMAT Question of the Day (Apr 8): Arithmetic and Sentence Correction

- Apr 8, 02:00 AM Comments [0]

Math (PS)

Which of the following is closest to $\frac{(998*0.02 + 4.97)}{(1002*0.02 + 5.03)}$ ?

(A) 0.50
(B) 0.89
(C) 0.98
(D) 1.02
(E) 1.05

Question Discussion & Explanation

GMAT Daily Deals
• Manhattan GMAT: 99 percentile teachers and superior curriculum at a more affordable price. Save @ GMAT Club. Save $325! • There's still a little time to save$50 on mbaMission Application Writing Bootcamps - Learn More. Learn More
• The Princeton Review teaches both material & testing strategies - not just the answers. Save \$350 @ GMAT Club. Learn More!

Verbal (SC)

Although it claims to delve into political issues, television can be superficial such as when each of the three major networks broadcast exactly the same statement from a political candidate.

(A) superficial such as when each of the three major networks
(B) superficial, as can sometimes occur if all of the three major networks
(C) superficial if the three major networks all
(D) superficial whenever each of the three major networks
(E) superficial, as when the three major networks each

Question Discussion & Explanation

Like these questions? Get the GMAT Club question collection: online at GMAT Club OR on your iPhone/iPad

Browse all GMAT Questions of the Day

Subscribe to GMAT Question of the Day: E-mail | RSS


text:
# polynomial approximation - basic chebyshev question

I was asked to find the best linear approximation to $f(x)=x^2$ in $x \in [0,1]$ using chebyshev polynomials, meaning, using the known property that $2^{1-n}T_n(x)$ is the best approximation to $0$ at $x \in [-1,1]$. (Where $T_n$ is chebyshev polynomial of degree $n$).

Before getting on to showing what I did, I would like to show a short solved example, so you have a better idea of what I'm talking about:

Example: We want to find the best linear approximation to $g(x)=x^3$ in $x \in [-1,1]$, we are given $T_3(x) = 4x^3-3x$

Using the known property of chebyshev polynomials, we know that $|2^{1-3}T_3(x)| = |t^3-\frac{3}{4}x|$ is the best approximation to zero, and so $\frac{3}{4}x$ is the best linear approximation to $x^3$.

We want to solve the original question in the same method, so first I transfered to $[-1,1]$:

let $t=2x-1$, $t \in [-1,1]$, so our original $f(x)=x^2$ now becomes $f(t)=(\frac{t+1}{2})^2=\frac{t^2+2t+1}{4}$

We want to find the best linear approximation to $f(t)=\frac{t^2+2t+1}{4}$ in $t \in [-1,1]$ using chebyshev polynomials.

But I don't see the connection. the second chebyshev polynomial is $T_2(t)=2t^2-1$. so we know $|t^2-\frac{1}{2}|$ is the best apprximation to zero, so $\frac{1}{2}$ is the best linear approximation to $t^2$. But that doesn't say anything about our original function, we are not interested in $t^2$, we are interested in $\frac{t^2+2t+1}{4}$.

I know the correct answer is $x-\frac{1}{8}$ but I don't know how to reach that answer.

Edit: Managed to solve it on my own. Sorry for bothering everyone. Will accept an answer to close this question.

• Nevermind, managed to solve it. had a "Eureka!" moment. – Oria Gruber Jan 21 '15 at 15:37

We showed that $\frac{1}{2}$ is the best linear approximation to $t^2$. It follows that $\frac{1}{2}+2t+1=\frac{3}{2}+2t$ is the best linear approximation to $t^2+2t+1$, and so
$\frac{3}{8}+\frac{1}{2}t$ is the best linear approximation to $\frac{t^2+2t+1}{4}$. Since we have $t=2x-1$, we find that $\frac{3}{8}+\frac{1}{2}t=x-\frac{1}{8}$ which is the desired result.
• The only thing I am unsure of is, if $\frac{1}{2}$ is the best linear approximation to $t^2$, then is it true that $\frac{1}{2}+2t+1$ is the best linear approximation to $t^2+2t+1$? Seems very intuitive and agree with common sense, but I have no formal proof. – Oria Gruber Jan 21 '15 at 15:46


text:
# A RLWE promise problem

Let $(R , \chi$) be a standard RLWE problem instance. I.e. $R$ is a finite degree polynomial ring over a finite field and $\chi$ is some gaussian distribution over R with small variance.

I wonder if the following promise problem is hard.
Let $a_0$ and $a_1$ be two random elements from $R$
The challenger choses a boolean $b$ and two elements $s,e \in \chi$, and calculates $c= a_b s + e$.

The problem is then:
Given $c, a_0, a_1$, calculate $b$ with non-negible advantage.

For motivation:
If that promise problem turns out to be hard, one could use as natural PQ replacement of PACE, the password authenticated key agreement protocol used in electronic passports. (See ICAO doc 9303)

• It feels like it ought to follow immediately from the standard rLWE assumption ("given $a$ and either $as + e$ or a random value $r$, it is hard to determine whether you received $as + e$ or $r$"); however I just can't see the reduction... Aug 13 '17 at 18:54
• @poncho: That is exactly my problem; I can also not see a reduction to RLWE decision. Meanwhile I think that this problem is weaker then RLWE decision/search.
– user27950
Aug 13 '17 at 19:02
• If you're looking for a RLWE-based PAKE, there's eprint.iacr.org/2016/552.pdf Aug 13 '17 at 19:14
• Thank you for the link. But I want to have a natural replacement for PACE.
– user27950
Aug 14 '17 at 3:58
• @Cryptostasis I think the use of a Boolean $b$ might make it weaker, but that could be contingent on the dimension of the lattice. Aug 18 '17 at 20:01

(It seems that the proof can be salvaged.)

Let $\text{RLWE}$ denote the standard ring-LWE problem where the secret $s$ is drawn uniformly at random from $R$. Thus, the $\text{RLWE}$ assumption is: $$(a,as+e)\approx(a,r):a,r,s\leftarrow R, e\leftarrow\chi,$$ where $\approx$ denotes computational indistinguishability. $\text{RLWE}$ assumption implies the non-standard LWE assumption [Lemma 2, ACPS09], denoted $\text{RLWE'}$, where the secret is drawn from $\chi$: $$(a,as+e)\approx(a,r):a,r\leftarrow R, s,e\leftarrow\chi.$$ The hardness of the promise problem, denoted $\text{RLWE''}$, follows by a hybrid argument (see below) assuming $\text{RLWE'}$ holds. Thus, the chain of reduction is: $$\text{RLWE}<\text{RLWE'}<\text{RLWE''}.$$

The hybrid argument. We want to show that the two distributions $$D_L:=(a_0,a_1,a_0s+e) \text{ and } D_R:=(a_0,a_1,a_1s+e)$$ are computationally indistinguishable, for $a_0,a_1\leftarrow R$ and $s,e\leftarrow \chi$. Consider the hybrid distribution $$D_H:=(a_0,a_1,r)$$ where $a_0,a_1,r\leftarrow R$. We show that $D_L\approx D_H$ and $D_H\approx D_R$, and it follows by transitivity that $D_L\approx D_R$.

To see that $D_L\approx D_H$, suppose for contradiction that it is not: that is there exists an algorithm $\mathsf{A}$ that distinguishes $D_L$ from $D_H$. We show that $\mathsf{A}$ can be used to break $\text{RLWE'}$. The reduction $\mathsf{R}$ is straightforward: given a $\text{RLWE'}$ challenge $(a,b)$ (where $a\leftarrow R$ and $b$ is either $as+e$ or $r$), $\mathsf{R}$ samples $a'\leftarrow R$ and sends $(a,a',b)$ to $\mathsf{A}$ and outputs to its challenger whatever $\mathsf{A}$ outputs. If $b=as+e$ then $\mathsf{A}$ simulates $D_L$; otherwise it simulates $D_H$.

The argument showing $D_H\approx D_R$ is similar.

References.

[ACPS09] Applebaum, Cash, Peikert and Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. CRYPTO 2009.

• In the question, I presume that $s\leftarrow\chi$ is a mistake. Aug 18 '17 at 10:01
• No, $s \leftarrow \chi$ is correct, see the NewHope paper eprint.iacr.org/2015/1092.pdf
– user27950
Aug 18 '17 at 10:26
• Ah. Then I don't think the above argument holds. Aug 18 '17 at 10:41
• The proof can be salvaged, it seems. Aug 21 '17 at 10:48
• Sorry, my comment was nonsense. I removed it.
– user27950
Aug 22 '17 at 11:36


text:
Averages of Unlabeled Networks: Geometric Characterization and Asymptotic Behavior

# Averages of Unlabeled Networks: Geometric Characterization and Asymptotic Behavior

\fnmsEric D. \snmKolaczyk\thanksrefm1label=e1]kolaczyk@bu.edu [    \fnmsLizhen \snmLin\thanksrefm2label=e2]lizhen.lin@nd.edu [    \fnmsSteven \snmRosenberg\thanksrefm1label=e3]sr@bu.edu [    \fnmsJackson \snmWalters\thanksrefm1label=e4]jackwalt@bu.edu [ Boston University\thanksmarkm1 and the University of Notre Dame\thanksmarkm2 Department of Mathematics and Statistics
Boston University, USA
Department of Applied and Computational
Mathematics and Statistics
The University of Notre Dame, USA
###### Abstract

It is becoming increasingly common to see large collections of network data objects – that is, data sets in which a network is viewed as a fundamental unit of observation. As a result, there is a pressing need to develop network-based analogues of even many of the most basic tools already standard for scalar and vector data. In this paper, our focus is on averages of unlabeled, undirected networks with edge weights. Specifically, we (i) characterize a certain notion of the space of all such networks, (ii) describe key topological and geometric properties of this space relevant to doing probability and statistics thereupon, and (iii) use these properties to establish the asymptotic behavior of a generalized notion of an empirical mean under sampling from a distribution supported on this space. Our results rely on a combination of tools from geometry, probability theory, and statistical shape analysis. In particular, the lack of vertex labeling necessitates working with a quotient space modding out permutations of labels. This results in a nontrivial geometry for the space of unlabeled networks, which in turn is found to have important implications on the types of probabilistic and statistical results that may be obtained and the techniques needed to obtain them.

[
\kwd
\startlocaldefs\endlocaldefs\runtitle

Averages of Unlabeled Networks

{aug}

, , , and

class=MSC] \kwd[Primary ]62E20 \kwd62G20 \kwd[; secondary ]53C20

fundamental domain \kwdFréchet mean \kwdgraphs

## 1 Introduction

Over the past 15-20 years, as the field of network science has exploded with activity, the majority of attention has been focused upon the analysis of (usually large) individual networks. See [21, 23, 29], for example. While it is unlikely that the analysis of individual networks will become any less important in the near future, it is likely that in the context of the modern era of ‘big data’ there will soon be an equal need for the analysis of (possibly large) collections of (sub)networks, i.e., collections of network data objects.

We are already seeing evidence of this emerging trend. For example, the analysis of massive online social networks like Facebook can be facilitated by local analyses, such as through extraction of ego-networks (e.g., [20]). Similarly, the Functional Connectomes Project, launched a few years ago in imitation of the data-sharing model long-common in computational biology, makes available a large number of fMRI functional connectivity networks for use and study in the context of computational neuroscience (e.g, [11]). It would seem, therefore, that in the near future networks of small to moderate size will themselves become standard, high-level data objects.

Faced with databases in which networks are the fundamental unit of data, it will be necessary to have in place a network-based analogue of the ‘Statistics 101’ tool box, extending standard tools for scalar and vector data to network data objects. The extension of such classical tools to network-based datasets, however, is not immediate, since networks are not inherently Euclidean objects. Rather, formally they are combinatorial objects, defined simply through two sets, of vertices and edges, respectively, possibly with an additional corresponding set of weights. Nevertheless, initial work in this area demonstrates that networks can be associated with certain natural Euclidean subspaces and furthermore demonstrates that through a combination of tools from geometry, probability theory, and statistical shape analysis it should be possible to develop a comprehensive, mathematically rigorous, and computationally feasible framework for producing the desired analogues of classical tools.

For example, in our recent work [19] we have characterized the geometry of the space of all labeled, undirected networks with edge weights, i.e., consisting of graphs , for weights , where equality with zero holds if and only if . This characterization allowed us in turn to establish a central limit theorem for an appropriate notion of a network empirical mean, as well as analogues of classical one- and two-sample hypothesis testing procedures. Other results of this type include additional work on asymptotics for network empirical means [30] and regression modeling with a network response variable, where for the latter there have been both frequentist [13] and Bayesian [18] proposals. Work in this area continues at a quick pace – see, for example, [2] which proposes a classification model based on network-valued inputs and [17] which proposes a nonparametric Bayes model for distributions on populations of networks. Earlier efforts in this space have focused on the specific case of trees. Contributions of this nature include work on central limit theorems in the space of phylogenetic trees [10, 4] and work by Marron and colleagues [32, 3] in the context of so-called object-oriented data analysis with trees.

To the best of our knowledge, all such work to date pertains to the case of labeled networks: that is, to networks in which the vertices have unique labels, e.g., . In fact, unlabeled networks have received decidedly less attention in the network science literature as a whole but nevertheless arise in various important settings. The quintessential example of how such networks may arise in practice arguably is that of the study of ego-centric network structure in social network analysis. There, traditionally, individuals (‘egos’) are surveyed for a list of other individuals (‘alters’) with whom they share a certain relationship (e.g., friendship, colleague, etc.) and only common patterns across networks in the structure of the relationships among the individuals within each network are of interest. This leads to analyses that either ignore vertex labels or for which vertex labels are simply not available (e.g., through de-identification). See [27], for example.

In this paper, our focus is on averages of unlabeled, undirected networks with edge weights. Adopting a perspective similar to that in our previous work [19], we (i) characterize a certain notion of the space of all such networks, (ii) describe key topological and geometric properties of this space relevant to doing probability and statistics thereupon, and (iii) use these properties to establish the asymptotic behavior of a generalized notion of an empirical mean under sampling from a distribution supported on this space. In particular, adopting the notion of a Fréchet mean, we establish a corresponding strong law of large numbers and a central limit theorem. In contrast to [19], where the corresponding space of networks was found to form a smooth manifold, here the lack of vertex labeling necessitates working with a quotient space modding out permutations of labels. As a result, we have only an orbifold – a more general geometric structure – which in turn is found to have important implications on the types of probabilistic and statistical results that may be obtained and the techniques needed to obtain them.

The nature of our work is in the spirit of statistics on manifolds and statistical shape analysis, which employs the geometry of manifolds or shape spaces for defining Fréchet means and developing large sample theory of their sample counterparts for inference. See [6] for a rather comprehensive treatment on the subject. Our approach to studying the entire family of networks subject to an equivalence relation under a group action, via forming the associated quotient or moduli space, is a common theme in modern geometry, including gauge theory [15], symplectic topology [28], and algebraic geometry [14, 31]. The appearance of orbifolds, often much more complicated than in our case, is quite common. Finally, there is a large literature on graph limits, for which substantial work has been done on analysis of appropriate spaces of networks (e.g., [25]). But the focus therein typically is, by definition, on the case of a single network asymptotically increasing in size. Here, the focus is on asymptotics in many networks, with the dimension fixed.

The organization of this paper is as follows. In Section 2 we present our characterization of the space of unlabeled networks. Results from our investigation of the asymptotic behavior of the Fréchet empirical mean are then provided in Section 3. While a strong law of large numbers is found to emerge under quite general conditions, establishing just when conditions dictated by the current state of the art for central limit theorems on manifolds hold turns out to be a decidedly more subtle exercise. This latter is the focus of Section 4. Some additional discussion of open problems may be found in Section 5. The Appendices discuss implementation issues for the theoretical results in the paper.

## 2 The space of unlabeled networks

Our ultimate focus in this paper is on a certain well-defined notion of an ‘average’ on elements drawn randomly from a ‘space’ of unlabeled networks and on the statistical behavior of such averages. Accordingly, we need to establish and understand the relevant topology and geometry of this space. We do so by associating labeled networks with vectors and mapping those to unlabeled networks through the use of equivalence classes in an appropriate quotient space. In this section we provide relevant definitions, characterization, and illustrations of this space of unlabeled networks.

### 2.1 The topological space of unlabeled networks

Let be a labeled, undirected graph/network with weighted edges and with vertices/nodes. We always think of as having elements, where some of the edge weights can be zero. We think of the edge weight between vertices and as the strength of some unspecified relationship between and .

Let be the group of permutations of A permutation of the vertex labels technically produces a new graph , but with no new information. To define precisely, note that the weight function can be thought of as a symmetric function , with the weight of the edge joining vertex and vertex in . Therefore the action of on is given by

 (σ⋅wG)(i,j)=wG(σ−1(i),σ−1(j)).

(The inverse guarantees that ) Note that for general , not all permutations of the entries of are of the form as may have distinct permutations and has elements

In summary, is defined to be the graph on vertices with weight function Let be the set of all labeled graphs with vertices. Then the quotient space

 Ud=Gd/Σd

is the space of unlabeled graphs, the object we want to study. This means that an unlabeled network is an equivalence class

 [G]:={σ⋅G:σ∈Σd}.

As we now explain, looks like an explicit subset of , and so is easy to picture. In contrast, the quotient space is difficult to picture. Nevertheless, as we describe in the following paragraphs, the topology of may be characterized through standard point-set topology techniques, with the conclusion that everything works as well as possible. Readers who wish can safely skip to the examples in Section 2.2.

Fix an ordering of the vertices , and take the lexicographic ordering on the set of edges. (Thus if or and ) Given this ordering, we get an injection

 α:Gd→RD,  α(G)=(w1(G),…,wD(G)),

where is the weight of the edge of . The image of is the first “octant” The Euclidean metric on pulls back via to the obvious metric on : two networks are close iff their edge weights are close. Similarly, the standard topology on (an open ball in is the intersection of an open -Euclidean ball with ) pulls back to a topology on (This just means that is open iff is open in This makes a homeomorphism.) Just as in , the metric and topology are compatible: a sequence of graphs/weight vectors in converges to a graph/weight vector in the topology of iff the distance from to goes to zero.

Via the bijection , the action of on transfers to an action on First, acts on by if corresponds to the edge and corresponds to the edge . Then acts on by Since we’ve arranged the actions to be compatible with , we get a well defined bijection :

 Ud=Gd/Σd\lx@stackrel¯¯¯α→OD/Σd, ¯¯¯¯α[G]=[α(G)].

From now on, we just denote by

To complete the topological discussion, we note that is a homeomorphism if we give both sides the quotient topology: for the map taking a graph to its equivalence class, a set is open iff is open in . The quotient topology on is defined similarly.

### 2.2 Examples of quotient spaces

As a warmup, we first give a simple example of a quotient space resulting from the action of a finite group on a Euclidean space. This particular example is important in providing a relevant non-network analogy to our network-based results. We will revisit it frequently throughout the paper.

###### Example 2.1.

The group acts on the plane by rotation counterclockwise by degrees: specifically, for and ,

 k⋅z=eikπ/2⋅z.

Thus etc. A point in the quotient space is the set The set is called the orbit of under Note that every orbit is a four element set except for the exceptional orbit

The closed first quadrant is a fundamental domain for this action; i.e., each orbit has a unique representative/element in , except possibly for the orbits of points on the boundary of . Orbits of boundary points like have two representatives in , while the origin of course has only one representative.

If we want to picture a set that is bijective to , we could take e.g. to be minus the positive -axis. This is not so helpful topologically or geometrically, as the points and have close representatives in , while their representatives and are not close in . In particular, the sequence does not converge in , but the orbits converge to in Thus does not give us a good picture of topologically.

In summary, it is much better to keep both positive axes in , and to consider as (in bijection with) with the boundary points and “glued together.” More precisely, we have a bijection

 β:F:=F(a,0)∼(0,a)→C/Z4,

where the denominator indicates that the two point set is one point of , while all other points of correspond to a single point in At the price of this gluing, we now have that is a homeomorphism: points are close in iff they are close in (Technical remarks: gets the quotient topology from the standard topology on and the obvious surjection and “close” refers to the Procrustean distance defined in Section 3.)

Although this seems a little involved, it is quite easy to perform the gluing in in rubber sheet topology: stretching the interior of to allow the gluing of the two axes shows that and hence is a cone. See Figure 1.

###### Example 2.2.

We work out in detail the case of a network with three vertices. This is a deceptively easy case, as implies that every permutation of the edge weights comes from a permutation in In higher dimensions, the details are more complicated.

We first describe the quotient space of unlabeled graphs directly, and then find a fundamental domain for inside the space of labeled graphs . The direct approach is more difficult, which motivates our concentrating on fundamental domains in the rest of the paper.

Note that acts freely on i.e., iff The subset

 O≠03={(x,y,z)∈O3:x≠y,x≠z,y≠z; and x,y,z≠0}

is an open 3-manifold which is dense in and with a free -action, so we get a smooth 3-manifold structure on the open dense set

Now let be the subset of consisting of graphs with ; i.e., the weight of the edge (which is lexicographically the first edge) from vertex to vertex is zero. Then is the subset of the -plane (i.e. ) given by The subgroup of permutations fixing edge fixes . acts freely on ( of) the set of graphs and fixes the diagonal line This is because Thus the quotient space is homeomorphic to a closed pie wedge. We think of as a stratified -manifold: it contains an open, dense set which is a -manifold, the two edges (minus the origin) which are -manifolds, and the origin as a -manifold.

Denote the equivalence class of a point in by Each equivalence class in contains six points. In general, the number of elements in an equivalence class equals , where is the stabilizer subgroup of

The three coordinate planes , etc. get glued under the action of . For example, and Each coordinate plane gets further glued, e.g., gets glued to . Thus the three coordinate planes get glued to one pie wedge. This pie wedge is glued onto as follows: given with , we declare the limit point of this sequence to be We make the similar definition if or This is clearly well defined. We make a similar definition if has , etc. and if has .

From now on, for expository reasons, we drop the automatic conditions from description of subsets of

Similarly, the three planes , get glued together (e.g., ). Note that e.g. if and For example is glued to These three planes intersect at the line . Thinking of the three planes as troughs with edge , the three troughs are glued together. The two sides of a trough are not glued to each other, but are glued to sides of two other troughs. As above, has limit point/is glued to if , etc. In particular, if , this is consistent with the previous gluing.

The final quotient is a stratified -manifold:

• The dense -dimensional piece is , which is topologically a -ball.

• With increasingly terse notation, the 2d strata are

(i)
;

(ii) ;

(iii) .

• The 1d strata are

(i) ;

(ii)
;

(iii) .

• The 0d stratum is

The point in the 1d stratum can be perturbed into a 2d stratum point or or into a 3d stratum point This agrees with the fact that the 1d stratum glues both to a trough (a 2d stratum) and to an open wedge in a coordinate plane, and that this 1d stratum also glues to the big cell.

It is easier to picture the quotient space of unlabeled networks by finding a fundamental domain inside for the action of As in the previous example, and detailed in Section 4, is a closed set such that the quotient map is a continuous surjection, a homeomorphism from the interior of to a dense set of unlabeled networks, and a finite-to-one map on the boundary of . Thus represents bijectively except for some gluings on the boundary. This is illustrated in Figure 2, where Again, the case is deceptively easy, as is a bijection even on

The situation is more complicated for graphs with 4 (or more) vertices. For , if we label the edges as , then the weight vectors and have the same distributions of ones and zeros, but correspond to binary graphs which are not in the same orbit of . In particular, the region is not a fundamental domain for the action of

While a fundamental domain is harder to find in high dimensions (see Section 4), the overall structure of for general is similar to the case, with just increased notation.

###### Theorem 2.3.

The space of unlabeled graphs is a stratified space.

###### Proof.

We just sketch the proof, since this result is not used below. We don’t need the technical definition of a stratified space, just a general understanding that consists of a sequence of -dimensional manifolds with boundary, with -dimensional strata glued coherently to (or higher) dimensional strata. The big open cell of dimension is Lower strata are characterized by the number of zero entries and the number of equal nonzero entries. More precisely, say the weight vector has zeros and entries equal to , entries equal to , with all distinct. Then belongs to a stratum of dimension

 D−k−t∑i=1si.

A higher dimensional stratum has a lower dimensional stratum as part of if a sequence of points in converges to a point in This can occur either by an entry in this sequence going to zero, or by entries in this sequence going to a common positive limit. ∎

By [24], is PL or Lipschitz homeomorphic to , but the proof does not give a cell decomposition of , much less of

## 3 Network averages and their asymptotic behavior

In this section we define the mean of a distribution on the space of networks and investigate the asymptotic behavior of the empirical (or sample) mean network based on an i.i.d sample of networks from . Statistical inference can be carried out based on the asymptotic distribution of the empirical mean. We illustrate with an example from hypothesis testing. The results of the previous section, characterizing the topology and geometry of the space of unlabeled networks, are essential for achieving our goals in this section.

### 3.1 Network averages through Fréchet means

Let be some distribution on a general metric space . One can define the Fréchet function on as

 f(p)=∫Mρ2(p,z)Q(dz)(p∈M). (3.1)

If is finite on and has a unique minimizer

 μ=argminpf(p), (3.2)

then is called the Fréchet mean of (with respect to the metric ). Otherwise, the minimizers of the Fréchet function form a Fréchet mean set . Given an i.i.d sample on , the empirical Fréchet mean can be defined by replacing with the empirical distribution , that is,

 μn=argminp1nn∑i=1ρ2(p,Xi). (3.3)

When is a manifold, one can equip with a metric space structure through an embedding into some Euclidean space or employing a Riemannian structure of . Respectively, can be taken to be the Euclidean distance after embedding (extrinsic distance) or the geodesic distance (intrinsic distance), giving rise to extrinsic and intrinsic means. Asymptotic theory for extrinsic and intrinsic analysis has been developed in [6],[8], [9], and applied to many manifolds of interest (see e.g., [5], [16]).

Now take , the space of unlabeled networks with nodes, our space of interest, and let be a distribution on . Given an i.i.d sample from , in order to define the Fréchet mean of and empirical Fréchet mean of , one needs an appropriate choice of distance on . Given the quotient space structure characterized in the previous section, i.e., , a natural choice for the distance is the Procrustean distance , where

 dP([→x],[→y]):=minσ1,σ2∈ΣddE(σ1⋅→x,σ2⋅→y), (3.4)

for unlabeled networks , with denoting the vectorized representation of a representative network . We recall that is the set of all labeled graphs with vertices and is the group of permutations of .

In order to carry out statistical inference based on , defined with respect to the distance (3.4), some natural and fundamental questions related to and need to be addressed, which we aim to do in the following subsections. Here are some of the most crucial ones:

• (Consistency.) What are the consistency properties of the network empirical mean , i.e., is a consistent estimator of the population Fréchet mean ? Can we establish some notion of a law of large numbers for ?

• (Uniqueness of Fréchet mean.) This question is concerned with establishing general conditions on for uniqueness of the Fréchet mean . In general this a challenging task – indeed, the lack of general uniqueness conditions for Fréchet means is still one of the main hurdles for carrying out intrinsic analysis on manifolds [22]. To date the most general results in the literature for generic manifolds [1] force the support of to be a small geodesic ball to guarantee uniqueness of the intrinsic Fréchet mean. We address this question for the space of unlabeled networks in Section 4.

• (CLT.) Once conditions for uniqueness of are provided, the next key question is whether one can derive the limiting distribution for for purposes of statistical inference, e.g., proving a central limit type of theorem for , which in turn might be used for hypothesis testing.

We first illustrate the difficult nature of these problems (in particular for question 2 above) through the example in Section 2, by explicitly constructing a distribution on that has non-unique Fréchet means.

###### Example 3.1 (Example C=R2/Z4 continued).

As in Example 2.1 in Section 2, the quotient is a cone. Working in polar coordinates and taking to be a fundamental domain, we consider probability distributions of the form , where

We can explicitly compute the Fréchet function with respect to . For , is a fundamental domain. For , . Then

 f(x)=∫Fθ||x−y||2ν(y)dy=1M(c1χ1r2−2c2χ2(θ)r+c3χ1),

where for , and .

The Fréchet mean occurs when , which is difficult to compute in general. Consider the special case

 ν(r,θ)=1Mexp(−(r−α)2)\enskip, (3.5)

where is a fixed constant, , ; this distribution for is plotted in Figure 3. The minimum for this occurs at

 r0=√2(2α+√πeα2(2α2+1)(erf(α)+1))π3/2eα2α(erf(α)+1)+π,

with arbitrary. When is large, . For , . This shows that has a circle’s worth of Fréchet means; the -independence of implies -independence of the Fréchet means. One can see this in Figure 4 where the Fréchet function is minimal and most blue on a circle of radius approximately 13.53 (corresponding to the red circle on the cone in Figure 3).

### 3.2 A strong law of large numbers

Before establishing the limiting distribution for , a natural first step is to explore the consistency properties of . Drawing on Theorem 3.3 in [6] for general metric spaces, we have the following result.

###### Theorem 3.1.

Let be a distribution on , let be the set of means of with respect to the Procrustean distance , and let be the set of empirical means with respect to a sample of unlabeled networks . Assume that the Fréchet function is everywhere finite. Then the following holds: (a) the Fréchet mean set is nonempty and compact; (b) for any , there exists a positive integer-valued random variable and a -null set such that

 CQn⊆CϵQ≐{p∈M:dP(p,CQ)<ϵ}∀ n≥N (3.6)

outside of ; (c) if is a singleton, i.e., the Fréchet mean is unique, then is a strongly consistent estimator of , or converges to almost surely.

###### Proof.

We first prove that every closed and bounded subset of is compact.

Let be a fundamental domain for the action of on , as defined in Section 4, with the associated projection . This map is continuous and a diffeomorphism on the interior of Take a closed and bounded set in . Because is continuous, is closed. We now show that is also bounded. is contained in a ball centered at some with radius , so for . Now say that the largest entry in (in any ordering of the entries of ) is If the largest entry in (in any ordering) is greater than , then , a contradiction. (This holds because under any permutation of the entries of , one entry in is greater than .) Thus for any choice of , Thus is contained in the ball of radius centered at the origin, and thus is bounded.

Since is a closed subset of , the closed and bounded set is compact. Since is continuous, is compact.

Then by Theorem 3.3 in [6], (a) and (b) follow.

Part (c) follows from [33] under the uniqueness of Fréchet mean.

### 3.3 A central limit theorem

The goal of this section is to derive a central limit theorem for the empirical Fréchet mean, as an important precursor for statistical inference. One of the key challenges is to establish geometric conditions on distributions on which ensure the uniqueness of the population Fréchet mean. We discuss and address the uniqueness issue in detail in Section 4. Here, our central limit theorem assumes that the uniqueness conditions of Section 4 are met.

Let be the projection from the space of labeled networks to the space of unlabeled networks.

###### Theorem 3.2.

Assume has support on a compact set defined in Theorem 4.1, so that the pushdown measure supported on has a unique Fréchet mean . Let be the empirical Fréchet mean of an i.i.d sample with respect to the distance (3.4). Let . Then we have

 √n(ϕ(μn)−ϕ(μ))L→N(0,Σ), (3.7)

where with the Hessian matrix

 Λ=(E[Dr,s∥ϕ(μ)−ϕ(X1)∥])r,s=1,…,D,

and is the covariance matrix of .

Here denotes the partial derivative with respect to the direction, denotes second partial derivatives, and means convergence in law or distribution.

###### Proof.

Let be a small open neighborhood of inside , so is an open subset of . Note that is a homeomorphism. By Theorem 4.1, the projection map is a Euclidean isometry. Therefore, for any vectorized network and , one has

 d2P([→x],[→z])=d2P(ϕ−1(→x),[→z])=∥→x−→z∥2,

where Thus is twice differentiable in for any . Tracing through the definition of the smooth structure on induced from the standard structure on , we see that is twice differentiable in Also note that by the consistency of (see Theorem 3.1), one has as . One can also verify the conditions (A5) and (A6) on the Hessian matrices of Theorem 2.2 in [7], and our Theorem follows. ∎

As an immediate consequence of this central limit theorem, we can define natural analogues of classical hypothesis tests. For example, consider the construction of a statistical test for two or more independent samples using the same framework. Assume that we have independent sets of networks on vertices, and consider the problem of testing whether or not these sets have in fact been drawn from the same population. Formally, we have independent samples , for and . Each of these populations has an unknown mean, denoted . Then, as a direct corollary to Theorem 3.2, we have the following asymptotic result.

###### Corollary 3.2.

Assume that the distributions satisfy the conditions of Theorem 3.2. Moreover, also assume that for every sample, with , and . Then, under , we have

 Tk:=k∑j=1nj(ϕ(μj,nj)−ϕ(μn))′ˆΞ−1(ϕ(μj,nj)−ϕ(μn))⟶χ2(k−1)D,

where denotes the empirical mean of the sample, represents the grand empirical mean of the full sample, and is a pooled estimate of covariance, with the ’s denoting the individual covariance matrices estimates of each subsample.

As previously noted, this central limit theorem and such corollaries hold only if the population Fréchet mean(s) is unique. This depends crucially on the nontrivial geometry of the space of unlabeled networks. The following section deals exclusively with this issue.

## 4 Geometric requirements for uniqueness of the Fréchet mean

Underlying the central limit theorem in Theorem 3.2, the basic question is: which compact subsets of have a unique Fréchet mean?

We have seen in Section 2 that may be difficult to work with, while a fundamental domain for the action of on the space of labeled networks seems more tractable. Indeed, finding the Fréchet mean for a distribution supported in is a standard center of mass calculation in Euclidean space. However, it is not clear that this Fréchet mean “upstairs” in projects to the Fréchet mean “downstairs” in the quotient space , because the metric used to compute Fréchet means downstairs is the Procrustean distance, which may or may not equal the Euclidean distance.

In this section, we find a fundamental domain by a standard procedure (Lemma 4.1), and find compact subsets for which the Fréchet mean upstairs is guaranteed to project to the Fréchet mean of , where is the projection of under the quotient/projection map . This is the content of the main result in this section (Theorem 4.1). We also show that this result in our special setup is an improvement of the best result for general Riemannian manifolds due to Afsari [1] (see Figure 6).

We now discuss the construction of a fundamental domain . A fundamental domain is characterized by: (i) every weight vector can be permuted by some to a network in , (ii) if has for , then (As a technical note, we always consider with respect to the induced topology on from the standard topology on ) Once has been constructed, we are guaranteed that the projection map restricts to a surjective map which is a homeomorphism from the interior of to (In fact, is a diffeomorphism on this region by definition of the smooth structure on )

It is convenient to center a choice of fundamental domain on a weight vector with trivial stabilizer.

###### Definition 4.1.

A vector is distinct if it has trivial stabilizer for the action of : i.e., if for all ,

A vector with trivial stabilizer is also called a vector with trivial automorphism group. Weight vectors with all different entries are distinct, which implies that the distinct vectors are dense in

For example, consider the two graphs and in Figure 5. Both share the same connectivity pattern (i.e., are isomorphic), but have different weight vectors. The weight vector of satisfies for . In contrast, for all , where is the weight vector of , because the two 20’s belong to nodes with different valences. Thus even though have the same set of weights, is distinct, while is not.

We now explain a standard procedure to construct a fundamental domain as one region in the Voronoi diagram of the orbit of a distinct vector. (Geometers call this a Dirichlet domain.) Let be the Procrustean distance on From now on, we just write instead of for elements of

###### Lemma 4.1.

Fix a distinct vector . Set

 F =F→w={→w′∈OD:dE(→w,→w′)≤dE(→w,σ⋅→w′), ∀σ∈Σd} ={→w′∈OD:dE(→w,→w′)=dP(→w,→w′)}.

Then

(i) is a fundamental domain for the action of on .

(ii) is a solid cone with polyhedral cross section.

In the proof, we use the fact that is distinct just below (4.1).

###### Proof.

(i) First, for fixed , a minimum of is attained, since is finite. Thus every network (characterized by its weight vector ) has a permutation in .

Second, we can rewrite as

 F={→w1∈OD:dE(→w,→w1)≤dE(σ⋅→w,→w1), ∀σ∈Σd}.

Let . Then , and

 dE(→w,→w1) =minτdE(→w,τ→w


text:
# Trapezium Rule

## Practise using the trapezium rule to find an approximate value for the area under a curve.

Answers with more than three significant figures should be rounded to three significant figures.

This exercise will take you step by step through the process of approximating the area of the curve defined by the following function:

$$y=\frac{24}{\left(x+5\right)}+3$$

The area is required between $$x=1$$ and $$x=5$$ and will be found by splitting this area into 4 regions that can be roughly drawn as trapeziums.

Complete the following table to show the ordinates, the lengths of the vertical sides of the trapeziums.

 $$x$$ $$y$$ 1 2 3 4 5

The four trapeziums can be numbered one to four from left to right. Calculate the areas of each of the trapeziums:

 Trapezium Area number 1 number 2 number 3 number 4

Add the areas together to find the total area of the green area under the curve.

Check

This is Trapezium Rule level 1. You can also try:
Level 2 Level 3

## Instructions

Try your best to answer the questions above. Type your answers into the boxes provided leaving no spaces. As you work through the exercise regularly click the "check" button. If you have any wrong answers, do your best to do corrections but if there is anything you don't understand, please ask your teacher for help.

When you have got all of the questions correct you may want to print out this page and paste it into your exercise book. If you keep your work in an ePortfolio you could take a screen shot of your answers and paste that into your Maths file.

## Transum.org

This web site contains over a thousand free mathematical activities for teachers and pupils. Click here to go to the main page which links to all of the resources available.

## More Activities:

Mathematicians are not the people who find Maths easy; they are the people who enjoy how mystifying, puzzling and hard it is. Are you a mathematician?

Comment recorded on the 1 February 'Starter of the Day' page by Terry Shaw, Beaulieu Convent School:

"Really good site. Lots of good ideas for starters. Use it most of the time in KS3."

Comment recorded on the 2 May 'Starter of the Day' page by Angela Lowry, :

"I think these are great! So useful and handy, the children love them.
Could we have some on angles too please?"

Each month a newsletter is published containing details of the new additions to the Transum website and a new puzzle of the month.

The newsletter is then duplicated as a podcast which is available on the major delivery networks. You can listen to the podcast while you are commuting, exercising or relaxing.

Transum breaking news is available on Twitter @Transum and if that's not enough there is also a Transum Facebook page.

##### Featured Activity

The Transum Newsletter for February 2023 has just been published. Click on the image above to read about the latest developments on this site and try to solve the puzzle of the month. You can read the newsletter online or listen to it by downloading the podcast.

There are answers to this exercise but they are available in this space to teachers, tutors and parents who have logged in to their Transum subscription on this computer.

A Transum subscription unlocks the answers to the online exercises, quizzes and puzzles. It also provides the teacher with access to quality external links on each of the Transum Topic pages and the facility to add to the collection themselves.

Subscribers can manage class lists, lesson plans and assessment data in the Class Admin application and have access to reports of the Transum Trophies earned by class members.

Subscribe

## Go Maths

Learning and understanding Mathematics, at every level, requires learner engagement. Mathematics is not a spectator sport. Sometimes traditional teaching fails to actively involve students. One way to address the problem is through the use of interactive activities and this web site provides many of those. The Go Maths page is an alphabetical list of free activities designed for students in Secondary/High school.

## Maths Map

Are you looking for something specific? An exercise to supplement the topic you are studying at school at the moment perhaps. Navigate using our Maths Map to find exercises, puzzles and Maths lesson starters grouped by topic.

## Teachers

If you found this activity useful don't forget to record it in your scheme of work or learning management system. The short URL, ready to be copied and pasted, is as follows:

Alternatively, if you use Google Classroom, all you have to do is click on the green icon below in order to add this activity to one of your classes.

It may be worth remembering that if Transum.org should go offline for whatever reason, there are mirror sites at Transum.com and Transum.info that contain most of the resources that are available here on Transum.org.

When planning to use technology in your lesson always have a plan B!

Do you have any comments? It is always useful to receive feedback and helps make this free resource even more useful for those learning Mathematics anywhere in the world. Click here to enter your comments.

For Students:

For All:

Scan the QR code below to visit the online version of this activity.

https://Transum.org/go/?Num=885

## Description of Levels

Close

Level 1 - A structured single question with many parts

Level 2 - Five practice questions

Level 3 - Questions requiring a little more thought

Exam-Style - Have a go at an IB/A-level exam-style questions (worked solutions are available for Transum subscribers).

Calculus a collection of lesson Starters, visual aids, investigations and self-marking exercises.

Answers to this exercise are available lower down this page when you are logged in to your Transum account. If you don’t yet have a Transum subscription one can be very quickly set up if you are a teacher, tutor or parent.

## Example

The video above comes from Revision Village

Sometimes the area under a curve cannot be found by integration. In these cases a method to approximate the area under the curve called the trapezium rule can be used.

The rule divides the area under a curve into trapeziums, calculates their areas, then sums these areas to get an approsimation of the total area.

## Trapezium Rule

If the width of each interval is $$h$$ and the y values (ordinates) are denoted as $$y_0, y_1, y_2, y_3 ...$$ then the formula for finding the sum of the areas of these trapeziums is

$$\frac12 h ((y_0 + y_n) + 2(y_1 + y_2 + ... + y_{n-1}))$$

where n is the number of intervals.

Note that the number or ordinates is always one more than the number of intervals.

If the lower bound of the required area is $$p$$ and the upper bound is $$q$$ then

$$h= \frac{q-p}{n}$$

The more trapeziums the area is divided into the more accurate the estimate.

When the gradient of the graph is increasing over the given interval the area given by the trapezium rule will be an overestimate of the actual area.

When the gradient of the graph is decreasing over the given interval the area given by the trapezium rule will be an underestimate of the actual area.

Don't wait until you have finished the exercise before you click on the 'Check' button. Click it often as you work through the questions to see if you are answering them correctly. You can double-click the 'Check' button to make it float at the bottom of your screen.

Answers to this exercise are available lower down this page when you are logged in to your Transum account. If you don’t yet have a Transum subscription one can be very quickly set up if you are a teacher, tutor or parent.

Close


text:
# Mind The Gaps

Geometry Level 3

The two large gray circles are congruent, and each is half the diameter of the largest circle. All circles that appear to be tangent to each other are indeed tangent to each other.

$\frac{\text{radius of blue circle}}{\text{radius of red circle}} = \frac{a}{b},$
where $a$ and $b$ are coprime positive integers. Find $a+b$.

×


text:
For positive $a$, $b$, $c$ such that $abc=1$. Show that $$(ab+bc+ca)(a+b+c)+6\geq 5(a+b+c).$$

From the LHS, using AM-GM, we see that $(ab+bc+ca)(a+b+c)+6\geq 3(abc)^{2/3}3(abc)^{1/3}+6=15$. But clearly, 15 can be less than $5(a+b+c)$. So this technique won't work. I fail to see some other inequalities to prove this. Any other ideas/hints? Thanks

• set $a=x/y,b=y/z,c=z/x$ – Dr. Sonnhard Graubner Dec 25 '15 at 2:12
• No. $5(a+b+c)$ cannot be less than $15$. – SinTan1729 Dec 25 '15 at 2:35
• @SayantanSantra The question has been edited. – user236182 Dec 25 '15 at 7:45
• By AM-GM $5(a+b+c)\ge 5(3\sqrt[3]{abc})=15$. So in fact, $15$ is always less than $5(a+b+c)$ (or equal if $a=b=c=1$). – user236182 Dec 25 '15 at 7:46

Lemma: for any postive $x,y,z>0$,and $xyz=1$ we have $$(xy+yz+xz)^2+3\ge 4xyz(x+y+z)$$ proof:since Use Schur inequality we have $$a^3+b^3+c^3+3abc\ge ab(a+b)+bc(b+c)+ac(a+c)\ge 2((ab)^{3/2}+(bc)^{3/2}+(ac)^{3/2})$$ take $a'^2=a^3,b'^2=b^3,c'^2=c^3$ and Assmue that $a'b'c'=1$so we have $$a'^2+b'^2+c'^2+3\ge 2(a'b'+b'c'+c'a'),$$ so $$(a'+b'+c')^2+3\ge 4(a'b'+b'c'+c'a')$$ Let $a'=xy,b'=yz,c'=zx$ by done.

let $a+b+c=p,ab+bc+ac=q,abc=r=1$,your inequality equal to $$pq+6\ge 5p$$ Use Lemma we have $$q^2+3\ge 4p$$ $$\Longleftrightarrow p\sqrt{4p-3}+6\ge 5p,p\ge 3$$ it is clear .Because $$p^2(4p-3)-(5p-6)^2=4(p-3)^2(p-1)\ge 0$$

• Thank you very much, appreciated – amathnerd Dec 25 '15 at 17:06

Let $a+b+c=3u$, $ab+ac+bc=3v^2$ and $abc=w^3$.

Hence, our inequality is a linear inequality of $u$, which says that it's enough to prove our inequality

for an extremal value of $u$, which happens for equality case of two variables.

Let $b=a$.

Thus, $z=\frac{1}{a^2}$ and we need to prove that $$(a-1)^2(2a^4+4a^3-4a^2-a+2)\geq0,$$ which is obvious.

Done!


text:
### CMOS GATES BASIC AND TUTORIALS

WHAT ARE CMOS GATES? HOW CMOS GATES WORK?

CMOS gates are based on simple modifications to the CMOS inverter.

Figure 8.18(a) and Figure 8.18(b) show that the CMOS NOR and NAND gates are essentially CMOS inverters in which the load and driving transistor are replaced by series or parallel combinations (as appropriate) of PMOS andNMOStransistors, respectively.

Suppose the NOR gate of Fig. 8.18(a) is to have the same VDD and Vinv as the CMOS inverter of Fig. 8.17(a), then the equivalent Zpu and Zpd for the NOR gate should equal those for the inverter.

Since only one of the parallel pull-down transistors needs be on in the NOR to ensure VO = 0V, ZI = Zpd = 1/2 , as for the inverter. For the series load, however, ZL = 1/10 to give equivalent Zpu = 1/5 .

If the NAND gate of Fig. 8.18(b) is to have the same Vinv as the said inverter, similar arguments lead to ZI = 1/4 and ZL = 1/5 for the NAND.

Thus, KR = 0.4 for the inverter, 0.2 for the NOR, and 0.8 (closer to unity) for NAND. Hence, NAND is the standard gate in CMOS.

Another way of putting this is that for the given Z values, if the channel length L is constant, then the widths of the loads for the inverter, NOR, and NAND are in the ratio 1:2:1.

Thus, the NOR requires more chip area, and this larger area requirement increases with the number of inputs.


text:
# Windows XP HOME will not remember password to shared network

A

#### Anders Boholdt-Petersen

Hi everyone,

After I have reboot my computer, Windows XP HOME will not remember my
password to a local shared network drive.

If I search after a solution via Google, I can see that I should check a box
there says "Remember this password", but I can not see this checkbox when I
connect to the shared network drive.

Have one in this newsgroup a solution, so I can save the password?

Both the shared network and the computer uses a workgroup called MS HOME.


text:
MathSciNet bibliographic data MR271721 (42 #6602) 46.35 Rosenthal, Haskell P. On the subspaces of \$L\sp{p}\$$L\sp{p}$ \$(p>2)\$$(p>2)$ spanned by sequences of independent random variables. Israel J. Math. 8 1970 273–303. Article

For users without a MathSciNet license , Relay Station allows linking from MR numbers in online mathematical literature directly to electronic journals and original articles. Subscribers receive the added value of full MathSciNet reviews.

Username/Password Subscribers access MathSciNet here

AMS Home Page

 American Mathematical Society 201 Charles Street Providence, RI 02904-6248 USA
© Copyright 2015, American Mathematical Society
Privacy Statement


text:
## TLE '17 Contest 5 P1 - Guess the Number

View as PDF

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Fax and Flaco are playing Guess the Number.

Fax McClad, Croneria's luckiest bounty hunter, is playing a guessing game with Flaco.

Flaco chooses an integer between and , inclusive. Then, Fax will repeatedly make guesses until he is certain what is.

Suppose Fax guesses . Then, Flaco will tell him that he is away from the answer.

There are a lot of Moneys on the line, and the fewer the guesses Fax makes, the more Moneys he will win! Please help Fax to determine what Flaco's secret number is!

#### Interaction

This is an interactive problem.

Output guess n to guess a number n. This number should be between and , inclusive. Then your program should read in an integer, which is the value of .

When you are sure about your answer, output answer n, where n is your answer, and terminate.

Each time you output a number, make sure to output a new line \n and flush your output buffers. You can use fflush(stdout) in C++, System.out.flush(); in Java, or import sys; sys.stdout.flush() in Python 2/3. For other languages, search in its documentation.

#### Sample Interaction

>>> denotes your output; don't actually print this out.

>>> guess 5
5
>>> guess 3
7
>>> guess 14
4
>>> guess 10
0
>>> guess 11
1
>>> answer 10

Note that guesses were made. That is, answer does not count as a guess.


text:
# Number Series Questions

Q:

Find the missing number in the series?

4, 18, ?, 100, 180, 294, 448

 A) 48 B) 50 C) 58 D) 60

Answer & Explanation Answer: A) 48

Explanation:

Take a Look at this series :

$23$ - $22$ =  8 - 4 = 4

$33$ - $32$ = 27 - 9 = 18

$43$ - $42$ = 64 - 16 = 48

$53$ - $52$ = 125 - 25 = 100

$63$ - $62$ = 216 - 36 = 180

$73$ - $72$ = 343 - 49 = 294

$83$ - $82$ = 512 - 64 = 448

Report Error

975 61750
Q:

Find the missing number in the following series?

3, 5, 5, 19, 7, 41, 9, ?

 A) 71 B) 61 C) 79 D) 69

Answer & Explanation Answer: A) 71

Explanation:

Fiest series : 3, 5, 7, 9

Second series : 5, 19, 41, ?

Difference of Second series are 14, 22, 30 etc

Next term is 41+30 i.e equal to 71

Report Error

564 59856
Q:

What should come in place of question mark (?) in the following number series?

132       156       ?         210          240          272

 A) 196 B) 182 C) 199 D) 204

Answer & Explanation Answer: B) 182

Explanation:

The given series follows a logic that

11 x 12, 12 x 13, 13 x 14, 14 x 15, 15 x 16,...

So the missing number is 13 x 14 = 182

Report Error

237 54847
Q:

Find the wrong number in the series.

1, 2, 6, 15, 31, 56, 91

 A) 31 B) 15 C) 56 D) 91

Answer & Explanation Answer: D) 91

Explanation:

The difference of the two consecutive numbers are 1, 4, 9, 16, 25, 35.

This is clearly ,

Here 35 is wrong, So our wrong number is 91

Report Error

287 44386
Q:

1, 2, 3, 10, ?, 9802

 A) 99 B) 199 C) 299 D) 999

Answer & Explanation Answer: A) 99

Explanation:

Report Error

634 40598
Q:

Find out the wrong term in the series 2, 3, 4, 4, 6, 8, 9, 12, 16

 A) 9 B) 12 C) 16 D) 8

Answer & Explanation Answer: A) 9

Explanation:

The given sequence is a combination of three series:
i)1st, 4th, 7th terms i.e, 2, 4, 9
ii)2nd, 5th, 8th terms i.e, 3, 6, 12
iii)3rd, 6th, 9th terms i.e, 4, 8, 16
In each one of i, ii, iii, each term is twice the preceding term.
So, 9 is wrong and must be replaced by (4*2) = 8

Report Error

306 29341
Q:

8, 15, 28, 53, ?, 199

 A) 101 B) 102 C) 103 D) 104

Answer & Explanation Answer: B) 102

Explanation:

Here the series of the form is

53 x 2 - 4 = 106 - 4 = 102

Report Error

214 26599
Q:

Find the wrong number in the series.

3, 8, 15, 24, 34, 48, 63

 A) 15 B) 24 C) 34 D) 48

Answer & Explanation Answer: C) 34

Explanation:

The difference between consecutive numbers of the given series are respectively 5, 7, 9, 11, 13, and 15.

Therefore, 24+11=35 But in your problem it is given as 34.so 34 is wrong number

Report Error

192 25112