text:
## A decagonal snowflake from pentagons

25 June 2017

So far in these posts about fractals, I’ve shown (1) how letting triangles reproduce like this:

generates a bunch of copes of the Koch snowflake at different scales:

Similarly, I’ve shown (2) how letting squares reproduce like this:

generates a bunch of copies of a fractal related to the Koch snowflake, but with 8-fold symmetry:

So what about letting pentagons reproduce?   For pentagons, an analog of the replication rules above is this:

Each of the 10 cute little pentagon children here is a factor of $\frac{1}{2+\varphi}$ smaller than its parent, where $\varphi$ is the golden ratio.

However, something interesting happens here that didn’t happen with the triangle and square rules. While triangles and squares overlap with their ancestors, pentagons overlap with both their ancestors and their cousins.  The trouble is that certain siblings already share faces (I know, the accidental metaphors here are getting troublesome too!), and so siblings’ children have to fight over territory:

In this three-generation pentagon family portrait, you can see that each second generation pentagon has two children that overlap with a cousin.

As we carry this process further, we get additional collisions between second cousins, third cousins, and so on.  At five generations of pentagons, we start seeing some interestingly complex behavior develop from these collisions:

There’s a lot of fascinating structure here, and much of it is directly analogous to the 6-fold and 8-fold cases above, but there are also some differences, stemming from the “cousin rivalry” that goes on in pentagon society.

Let’s zoom in to see some collisions near where the two ‘wreaths’ meet on the right side of the picture:

I find the complicated behavior at the collisions quite pretty, but the ordering issues (i.e. which members of a given generation to draw first when they overlap) annoy me somewhat, since they break the otherwise perfect decagonal symmetry of the picture.

If I were doing this for purely artistic purposes, I’d try resolving the drawing order issues to restore as much symmetry as possible. Of course, I could also cheat and restore symmetry completely by not filling in the pentagons, so that you can’t tell which ones I drew first:

It’s cool seeing all the layers at once in this way, and it shows just how complex the overlaps can start getting after a few generations.

Anyway, because of these collisions, we don’t get seem to get a fractal tiling of the plane—at least, not like we got in the previous cases, where the plane simply keeps getting further subdivided into regions that converge to tiles of the same shape at different scales.

Actually, though, we still might get a fractal tiling of the plane, if the total area of overlap of nth generation pentagons shrinks to zero as n goes to infinity!  That would be cool.  But, I don’t know yet.

In any case, the picture generated by pentagons is in many ways very similar to the pictures generated by triangles and squares. Most importantly, all of the similar-looking octagonal flower shaped regions we see in this picture including the outer perimeter, the inner light-blue region, and tons of smaller ones:

really are converging to the same shape,  my proposal for the 10-fold rotationally symmetric analog of the Koch snowflake:

How do we know that all of these shapes are converging to the same fractal, up to rescaling?  We can get a nice visual proof by starting with two pentagons, one rotated and scaled down from the other, and then setting our replication algorithm loose on both of them:

Proof:

We see that the area between the two fractal curves in the middle shrinks closer to zero with each generation.

Puzzle for Golden Ratio Fans: What is the exact value of the scaling factor relating the two initial pentagons?

Next up in this infinite series of articles: hexagons!  …

I’m joking!  But, it’s fairly clear we can keep ascending this ladder to get analogs of the Koch snowflake generated by n-gons, with (2n)-fold rotational symmetry.  More nice features might be sacrificed as we go up; in the case generated by hexagons, we’d have collisions not only between cousins, but already between siblings.

## More fractal fun

23 June 2017

In the previous article, I explained how the famous Koch snowflake can be built in a different way, using “self-replicating” triangles. This was a revelation for me, because I had always thought of the Koch snowflake as fundamentally different from other kinds of fractals like the Sierpinski triangle, and now I think of them as being basically the same.

In the Sierpinski triangle, each triangle yields three new, scaled-down triangles, attached at the midpoints of sides of the original, like this:

These triangles are usually thought of as “holes” cut out of a big triangle, but all I care about here is the pattern of the triangles.  As I explained last time, the Koch snowflake can be built in a similar way, where each triangle produces six new ones, like this:

You might say this bends the usual rules for making fractals since some of the triangles overlap with their ancestors.  But, it makes me happy because it lets me think of the Sierpinski triangle and the Koch snowflake as essentially the same kind of thing, just with different self-replication rules.

What other fractals can we build in this way?  The Sierpinski carpet is very similar to the Sierpinski triangle, where we now start with squares and a rule for how a square produces 8 smaller ones:

This made me wonder if I could generalize my construction of the Koch snowflake using triangles to generate some other fractal using squares.  In other words, is there some Koch snowflake-like fractal that is analogous to the ordinary Koch snowflake in the same way that the Sierpinski carpet is analogous to the Sierpinki traingle?

There is!  Taken to the 5th generation, it looks like this:

The outline of this fractal is an analog of the Koch snowflake, but with 8-fold symmetry, rather than 6-fold.  Compare the original Koch snowflake with this one:

Just as I explained last time for the Koch snowflake (left), the blue picture above actually provides a proof that the plane can be tiled with copies of tiles like the one on the right, with various sizes—though in this case, you can’t do it with just two sizes of tiles; it takes infinitely many different sizes!  In fact, this tiling of the plane is also given in Aidan Burns’ paper I referenced in the previous post.

But, my construction is built entirely out of self-replicating squares.  What’s the rule for how squares replicate?

Before I tell you, I’ll give two hints:

First, each square produces 8 new squares, just like in the Sierpinski carpet.  (So, we could actually make a cool animation of this fractal morphing into the Sierpinski carpet!)

Second, you can more easily see some of the bigger squares in the picture if you make the colors of the layers more distinct.  While I like the subtle effect of making each successive generation a slightly darker shade of blue, playing with the color scheme on this picture is fun.  And I learned something interesting when my 7-year old (who is more fond of bold color statements) designed this scheme:

The colors here are not all chosen independently; the only choice is the color of each generation of squares.  And this lets us see bits of earlier-generation squares peeking through in places I hadn’t noticed with my more conservative color choices.

For example, surrounding the big light blue flower in the middle, there are 8 small light blue flowers, and 16 even smaller ones (which just look like octagons here, since I’ve only gone to the 5th generation); these are really all part of the same light-blue square that’s hiding behind everything else.

The same thing happens with the pink squares, and so on.  If you stare at this picture, you can start seeing the outlines of the squares.

So what’s the rule?  Here it is:

## Fun with the Koch snowflake

22 June 2017

I was playing with fractals recently and discovered a fun way to construct the Koch snowflake. It may not be new to the world, given how much is known about fractals, but it was new to me. In any case, it’s really cool!  It lets you see a lot more interesting self-similarity in this fractal, and effortlessly leads to the known tilings of the plane by Koch snowflakes.

The  Koch snowflake is usually constructed starting with an equilateral triangle by replacing the middle third of each side with an equilateral triangular protrusion, doing this again to the resulting polygon, and so on.  The first seven steps are shown in this animation:

and the Koch snowflake is the “limit” of this process as the number of steps goes to infinity.

In the alternative construction we use only self-replicating triangles.  We again start with a triangle:

But now, rather than modifying this triangle, we let it “reproduce,” yielding  six new triangles, three at the corners of the original, and three sticking out from the sides of the original.  I’ll make the six offspring a bit darker than the original so that you can see them all:

Notice that three of the children hide the corners of their parent triangle, so it looks like we now have a hexagon in the middle, but really we’ve got one big triangle behind six smaller ones.  Now we do the same thing again, letting each of the six smaller triangles reproduce in the same way:

The 36 small triangles are the “grandchildren” of the original triangle; if each of these has six children of its own, we get:

Repeating this again:

And again:

At this stage, it starts getting hard to see the new triangles, so I’ll stop and rely on your imagination of this process continuing indefinitely.  We can now see some interesting features emerging.  Here are some of the main ones:

1. The outer perimeter of all of these triangles, taken to the infinite limit, is the Koch snowflake.
2. The lightest blue region, in the middle, is also converging to a smaller Koch snowflake, rotated from the outer one by $\pi/6$.
3. Between the outer perimeter and the Koch snowflake in the middle are six more yet smaller Koch snowflakes.
4. The regions in the middle of these snowflakes are also Koch snowflakes …

and so on: we have Koch snowflakes repeating at smaller and smaller scales.

All this self similarity shows in particular that Koch snowflakes can be assembled out of Koch snowflakes.  This is nothing new; it’s related to Aidan Burns’ nice demonstration that Koch snowflakes can be used to tile the plane, but only if we use snowflakes of at least two different sizes:

Aidan Burns, Fractal tilings. Mathematical Gazette 78 No. 482 (1994) 193–196.

These tilings are already visible in the above construction using triangles, but we can make them even more evident by just playing with the color scheme.

First, if we draw the previous picture again but make all of the triangles the same color, we just get a region whose perimeter is the usual Koch snowflake:

On the other hand, if we make the original triangle white, but all of its descendants the same color of blue, we get this:

I hope you see how this forms part of a wallpaper pattern that could be extended in all directions, adding more blue snowflakes that bound larger white snowflake-shaped gaps. This gives the tiling of the plane by Koch snowflakes of two different sizes.

Taking this further, if we make the the original triangle and all of its children white, but all of their further descendants the same color of blue, we get this:

The pattern seen here can be extended in a hopefully obvious way to tile the whole plane with Koch snowflakes of three different sizes.

Going further, if we make the first three generations white, but all blue after that, we get:

and so on.

The previous four pictures are generated with exactly the same code—we’re drawing exactly the same triangles, and only changing the color scheme.  If we keep repeating this process, we get a tiling with arbitrarily small Koch snowflakes!

But we can also go the other way, continuing up in scale to get a tiling that includes arbitrarily large Koch snowflakes.  To do this, we just need to view the above series of pictures in a different way!

The way I described it, the scale is the same in all of the previous four pictures.   Making successive generations white, one generation at a time, makes it look as if we’re cutting out a snowflake from the middle of a big snowflake, leaving six similar snowflakes behind, and then iterating this:

On the other hand, we can alternatively view these pictures as a process of zooming out: each picture is built from six copies of the previous one, and we can imagine zooming out so that each picture becomes just one small piece of the next:

etc.

If you’re careful about how you do this, you get a tiling of the whole plane, with arbitrarily large Koch-snowflake shaped tiles!  I say you have to be careful because it won’t cover the whole plane if, for example, each picture becomes the top middle part of the next picture.  But, if you zoom out in a “spiral,” rotating by $\frac{\pi}{3}$ at each step, you’ll get a tessellation of the plane.

Someone should make an animation that shows how this works.  Maybe I’ll get a student to do it.

There are some other fun variations on this theme—including a similar construction that leads to the other “fractal tiling” described by Aidan Burns—which I should explain in another post.

In case anyone wants it, here is a 1-page visual explanation of the construction described in this post: snowflake.pdf

(All images in this post, except for the first, copyright 2017 Derek Wise.)

## 4!-torsor a la George Hart

20 April 2015

As a project with a certain 4-year-old relative of mine, we constructed the proof I described before that the outer vertices of George Hart’s 12-Card Star form a 4!-torsor.  (I guess I didn’t say it that way before, but it’s true!)  Here’s our proof:

Last time I suggested using a deck of 12 cards like this:

But instead, we used four solid colors, three cards of each.  So, our “star” permutes the colors red, white, black, and silver:

You can get any permutation of these colors in our Star by exactly one symmetry taking outer vertices to outer vertices.  The “exactly one” in this isomorphism is what makes the set of outer vertices a 4!-torsor rather than just a 4!-set.

Here’s what it looks like when you put three pieces together, from both sides:

## George Hart’s “12-Card Star” and suit permutations.

7 March 2015

When I was at the JMM in San Antonio in January, I was happy to catch a workshop by George Hart:

I went to some great talks at the JMM, but a hands-on, interactive workshop was a nice change of pace in the schedule. Having seen some of George’s artwork before, I couldn’t resist. In the workshop, he taught us to build his sculpture/puzzle which he calls the 12 Card Star. Here’s what mine looked like:

He supplied the necessary materials: 13 decks of cards, all pre-cut (presumably with a band saw), like this:

We each took 13 card from these decks—the 13th, he said, was “just in case something terrible happens.”

He showed us how to put three cards together:

Then he gave us a clue for assembling the star: the symmetry group is the same as that of a …

Wait! Let’s not give that away just yet. Better, let’s have some fun figuring out the symmetry group.

Let’s start by counting how many symmetries there are. There are twelve cards in the star, all identically situated in relation to their neighbors, so that’s already 12 symmetries: given any card, I can move it to the position of my favorite card, which is the one I’ll mark here with a blue line along its fold:

But my favorite card also has one symmetry: I can rotate it 180$^\circ$, flipping that blue line from end to end around its midpoint, and this gives a symmetry of the whole star. (Actually, this symmetry is slightly spoiled since I drew the five of hearts: that heart right in the middle of the card isn’t symmetric under a 180$^\circ$ rotation, but never mind that. This would be better if I had drawn a better card, say the two of hearts, or the five of diamonds.)

So there are $12\times 2 = 24$ symmetries in total, and we’re looking for a group of order 24. Since 24 = 4!, the most obvious guess is the group of permutations of a 4-element set. Is it that? If so, then it would be nice to have a concrete isomorphism.

By a concrete isomorphism, I mean a specific 4-element set such that a permutation of that set corresponds uniquely to a symmetry of the 12-card star. Where do we get such a 4-element set? Well, since there are conveniently four card suits, let’s get a specific isomorphism between the symmetry group of Hart’s star and the group of permutations of the set

At the workshop, each participant got all identical cards, as you can see in the picture of mine. But if I could choose, I’d use a deck with three 2’s of each suit:

From this deck, there is an essentially unique way to build a 12-Card Star so that the isomorphism between the symmetry group and the group of permutations of suits becomes obvious! The proof is constructive,’ in that to really convince yourself you might need to construct such a 12-card star. You can cut cards using the template on George’s website. He’s also got some instructions there. But here I’ll tell you some stuff about the case with the deck of twelve 2’s. % and from these it will be clear that (if you succeed) your star will have the desired properties.

First notice that there are places where four cards come together, like this:

In fact, there are six such places—call these the six 4-fold rotation points—and it’s no coincidence that six is also the number of cyclic orderings of card suits:

Now, out of the deck of twelve 2’s, I claim you can build a 12-card star so that each of these cyclic orderings appears at one 4-fold rotation point, and that you can do it in an essentially unique way.

This should be enough information to build such a 12-card star. If you do, then you can check the isomorphism. Think up an permutation of the set of suits, like this one:

and check that you can rotate your 12-card star in such a way that all of the suit symbols on all of the cards in the 12-card star are permuted in that way.  The rest follows by counting.

Sometime I should get hold of the right cards to actually build one like this.

Of course, there are other ways to figure out the symmetry group. What George Hart actually told us during the workshop was not that the symmetry group was the permutation group on 4 elements, but rather that the symmetry group was the same as that of the cube. One way to see this is by figuring out what the convex hull’ of the 12-card star is. The convex hull of an object in Euclidean space is just the smallest convex shape that the object can fit in. Here it is:

This convex polyhedron has eight hexagonal faces and six square faces. You might recognize as a truncated octahedron, which is so named because you can get it by starting with an octahedron and cutting off its corners:

The truncated octahedron has the same symmetry group as the octahedron, which is the same as the symmetry group of the cube, since the cube and octahedron are dual.

Thanks to Chris Aguilar for the Vectorized Playing Cards, which I used in one of the pictures here.

## From the Poincaré group to Heisenberg doubles

25 September 2014

There’s a nice geometric way to understand the Heisenberg double of a Hopf algebra, using what one might call its “defining representation(s).” In fact, it’s based on the nice geometric way to understand any semidirect product of groups, so I’ll start with that.

First, consider the Poincaré group, the group of symmetries of Minkowski spacetime.  Once we pick an origin of Minkowski spacetime, making it into a vector space $\mathbb{R}^{3,1}$, the Poincaré group becomes a semidirect product

$\mathrm{ISO}(3,1)\cong\mathbb{R}^{3,1} \rtimes \mathrm{SO}(3,1)$

and the action on $\mathbb{R}^{3,1}$ can be written

$(v,g)\cdot x = v + g x$

In fact, demanding that this be a group action is enough to determine the multiplication in the Poincaré group.  So, this is one way to think about the meaning of the multiplication law in the semidirect product.

In fact, there’s nothing so special about Minkowski spacetime in this construction.  More generally, suppose I’ve got a vector space $V$ and a group $G$ of symmetries of $V$.   Then $V$ acts on itself by translations, and we want to form a group that consists of these translations as well as elements of $G$.  It should act on $V$ by this formula:

$(v,g)\cdot x = v + g x$

Just demanding that this give a group action is enough to determine the multiplication in this group, which we call $V \rtimes G$.   I won’t bother writing the formula down, but you can if you like.

In fact, there’s nothing so special about $V$ being a vector space in this construction.  All I really need is an abelian group $H$ with a group $G$ of symmetries.  This gives us a group $H\rtimes G$, whose underlying set is $H \times G$, and whose multiplication is determined by demanding that

$(h,g) \cdot h' = h + gx$

is an action.

In fact, there’s nothing so special about $H$ being abelian.  Suppose I’ve got a group $H$ with a group $G$ of symmetries.  This gives us a group $H\rtimes G$, built on the set $H \times G$, and with multiplication  determined by demanding that

$(h,g)\cdot x = h (g x)$

give an action on $H$.  Here $gx$ denotes the action of $g\in G$ on $x\in H$, and $h(gx)$ is the product of $h$ and $gx$.

For example, if $H$ is a group and $G=\mathrm{Aut}(H)$ is the group of all automorphisms of $H$, then the group $H\rtimes \mathrm{Aut}(H)$ is called the holomorph of $H$.

What I’m doing here is defining $H \rtimes G$ as a concrete group: it’s not just some abstract group as might be defined in an algebra textbook, but rather a specific group of transformations of something, in this case transformations of $H$.  And, if you like Klein Geometry, then whenever you see a concrete group, you start wondering what kind of geometric structure gets preserved by that group.

So: what’s the geometric meaning of the concrete group $H \rtimes G$?  This really involves thinking of $H$ in two different ways: as a group and as a right torsor of itself.  The action of $G$ preserves the group structure by assumption: it acts by group automorphisms.  On the other hand, the action of $H$ by left multiplication is by automorphisms of $H$ as a right $H$ space.  Thus,  $H \rtimes G$ preserves a kind of geometry on $H$ that combines the group and torsor structures.  We can think of these as a generalization of the “rotations” and “translations” in the Poincaré group.

But I promised to talk about the Heisenberg double of a Hopf algebra.

In fact, there’s nothing so special about groups in the above construction.  Suppose $H$ is a Hopf algebra, or even just an algebra, and there’s some other Hopf algebra $G$ that acts on $H$ as algebra automorphisms.  In Hopf algebraists’ lingo, we say $H$ is a “$G$ module algebra”.  In categorists’ lingo, we say $H$ is an algebra in the category of $G$ modules.

Besides the Hopf algebra action, $H$ also acts on itself by left multiplication.  This doesn’t preserve the algebra structure, but it does preserve the coalgebra structure: $H$ is an $H$ module coalgebra.

So, just like in the group case, we can form the semidirect product, sometimes also called a “smash product” in the Hopf algebra setting, $H \rtimes G$, and again the multiplication law in this is completely determined by its action on $H$. We think of this as a “concrete quantum group” acting as two different kinds of “quantum symmetries” on $H$—a “point-fixing” one preserving the algebra structure and a “translational” one preserving the coalgebra structure.

The Heisenberg double is a particularly beautiful example of this.   Any Hopf algebra $H$ is an $H^*$ module algebra, where $H^*$ is the Hopf algebra dual to $H$.  The action of $H^*$ on $H$ is the “left coregular action” $\rightharpoonup$ defined as the dual of right multiplication:

$(h\rightharpoonup \alpha)(k) = \alpha(kh)$

for all $h,k\in H$ and all $\alpha \in H^*$.

One could use different conventions for defining the Heisenberg double, of course, but not as many as you might think.  Here’s an amazing fact:

$H \rtimes H^* = H \ltimes H^*$

So, while I often see $\rtimes$ and $\ltimes$ confused, this is the one case where you don’t need to remember the difference.

But wait a minute—what’s that “equals” sign up there.   I can hear my category theorist friends snickering.  Surely, they say, I must mean $H \rtimes H^*$ is isomorphic to $H \rtimes H^*$.

But no.  I mean equals.

I defined $H \rtimes H^*$ as the algebra structure on $H \otimes H^*$ determined by its action on $H$, its “defining representation.”   But every natural construction with Hopf algebras has a dual.  I could have instead defined an algebra $H \ltimes H^*$ as the algebra structure on $H \otimes H^*$ determined by its action on $H^*$.  Namely, $H^*$ acts on itself by right multiplication, and $H$ acts on $H^*$ by the right coregular action.  These are just the duals of the two left actions used to define $H \rtimes H^*$.

That’s really all I wanted to say here.  But just in case you want the actual formulas for the Heisenberg double and its defining representations, here they are in Sweedler notation:

## Hopf algebroids and (quantum) groupoids (Part 2)

8 September 2014

Last time I defined weak Hopf algebras, and claimed that they have groupoid-like structure. Today I’ll make that claim more precise by defining the groupoid algebra of a finite groupoid and showing that it has a natural weak Hopf algebra structure. In fact, we’ll get a functor from finite groupoids to weak Hopf algebras.

First, recall how the group algebra works. If G is a group, its group algebra is simply the vector space spanned by elements of G, and with multiplication extended linearly from G to this vector space. It is an associative algebra and has a unit, the identity element of the group.

If G is a groupoid, we can similarly form the groupoid algebra. This may seem strange at first: you might expect to get only an algebroid of some sort. In particular, whereas for the group algebra we get the multiplication by linearly extending the group multiplication, a groupoid has only a partially defined “multiplication”—if the source of g differs from the target of h, then the composite gh is undefined.

However, upon “linearizing”, instead of saying gh is undefined, we can simply say it’s zero unless s(g)=t(h). This is essentially all there is to the groupoid algebra.  The groupoid algebra $\mathbb{C}[G]$ of a groupoid $G$ is the vector space with basis the morphisms of $G$, with multiplication given on this basis by composition whenever this is defined, zero when undefined, and extended linearly from there.

It’s easy to see that this gives an associative algebra: the multiplication is linear since we define it on a basis and extend linearly, and it’s associative since the group multiplication is. It is a unital algebra if and only if the groupoid has finitely many objects, and in this case the unit is the sum of all of the identity morphisms.

Mainly to avoid saying “groupoids with finitely many morphisms”, I’ll just stick to finite groupoids from now on, where the sets of objects and morphisms are both finite.

If we have a groupoid homomorphism, then we get an algebra homomorphism between the corresponding groupoid algebras, also by linear extension. So we get a functor

$\mathbb{C}[\cdot]\colon\mathbf{FinGpd} \to \mathbf{Alg}$

from the category of finite groupoids to the category of unital algebras.

But in fact, this extends canonically to a functor

$\mathbb{C}[\cdot]\colon\mathbf{FinGpd} \to \mathbf{WHopf}$

from the category of finite groupoids to the category of weak Hopf algebras.

To see how this works, notice first that there’s a canonical functor

$\mathbb{C}[\cdot]\colon\mathbf{Set} \to \mathbf{Coalg}$

from the category of sets to the category of coalgebras:  Every set is a comonoid in a unique way, so we just linearly extend that comonoid structure to a coalgebra.

In case that’s not clear to you, here’s what I mean in detail.  Given a set $X$, there is a unique map $\Delta\colon X \to X \times X$ that is coassociative, namely the diagonal map $\Delta(x) = (x,x)$. This is easy to prove, so do it if you never have.  Also, there is a unique map to the one-element set $\epsilon\colon X \to \{0\}$, up the choice of which one-element set to use.  Linearly extending $\Delta$ and $\epsilon$, they become a coalgebra structure on the vector space with basis $X$. Moreover, any function between sets is a homomorphism of comonoids, and its linear extension to the free vector spaces on these sets is thus a homomorphism of coalgebras.  This gives us our functor from sets to coalgebras.

So, given a finite groupoid, the vector space spanned by its morphisms becomes both an algebra and a coalgebra.  An obvious question is: do the algebra and coalgebra structure obey some sort of compatibility relations?  The answer, as I already gave away at the beginning, is that they form a weak Hopf algebra.  The antipode is just the linear extension of the inversion map $g \mapsto g^{-1}$.

(More generally, for those who care, the category algebra $\mathbb{C}[C]$ of a finite category $C$ (or any category with finitely many objects) is a weak bialgebra, and we actually get a functor

$\mathbb{C}[\cdot] \colon \mathbf{FinCat} \to \mathbf{WBialg}$

from finite categories to weak bialgebras.  If $C$ happens to be a groupoid, $\mathbb{C}[C]$ is a weak Hopf algebra; if it happens to be a monoid, $\mathbb{C}[C]$ is a bialgebra; and if it happens to be a group, $\mathbb{C}[C]$ is a Hopf algebra. )

This is nice, but have we squashed out all of the lovely “oid”-iness from our groupoid when we form the groupoid algebra? In other words, having built a weak Hopf algebra on the vector space spanned by morphisms, is there any remnant of the original distinction between objects and morphisms?

As I indicated last time, the key is in these two “loop” diagrams:

The left loop says to comultiply the identity, multiply the first part of this with an element $g$ and apply the counit. Let’s do this for a groupoid algebra, where $1 = \sum_x 1_x$, where the sum runs over all objects $x$.  Since comultiplication duplicates basis elements, we get

$\Delta(1) = \sum_x 1_x \otimes 1_x$

We then get:

$g\mapsto \sum_x \epsilon(1_x\cdot g) \otimes 1_x = 1_{t(g)}$

using the definition of multiplication and the counit in the groupoid algebra.  Similarly, the loop going in the other direction gives $g \mapsto 1_{s(g)}$, as anticipated last time.

So, we can see that the image of either of the two “loop” diagrams is the subspace spanned by the identity morphisms.  This is a commutative subalgebra of the groupoid algebra, and these maps are both idempotent algebra homomorphisms.  So, they give “projections” onto the “algebra of objects”.

In fact, something like this happens in the case of a more general weak Hopf algebra.  The maps described by the “loop” diagrams, are again idempotent homomorphisms and we can think of them as analogs of the source and target maps.  But there are some differences, too.  For instance, their images need not be the same in general, though they are isomorphic.  The images also don’t need to be commutative.  This starts hinting at what Hopf algebroids are like.

But I’ll get into that later.

## Hopf algebroids and (quantum) groupoids (Part 1)

1 September 2014

I’ve been thinking a lot about weak Hopf algebras and Hopf algebroids, especially in relation to work I’m doing with Catherine Meusburger on applications of them to gauge theory.  I don’t want to talk here yet about what we’re working on, but I do feel like explaining some basic ideas.  This is all known material, but it’s fun stuff and deserves to be better known.

First of all, as you might guess, the “-oid” in “Hopf algebroid” is supposed to be like the “-oid” in “groupoid”.  Groupoids are a modern way to study symmetry, and they do things that ordinary groups don’t do very well.  If you’re not already convinced groupoids are cool—or if you don’t know what they are—then one good place to start is with Alan Weinstein’s explanation of them here:

There are two equivalent definitions of groupoid, an algebraic definition and a categorical definition.  I’ll use mainly categorical language.  So for me, a groupoid is a small category in which all morphisms are invertible.  A group is then just a groupoid with exactly one object.

Once you’ve given up the attachment to the special case of groups and learned to love groupoids, it seems obvious you should also give up the attachment to Hopf algebras and learn to love Hopf algebroids.  That’s one thing I’ve been doing lately.

My main goal in these posts will be to explain what Hopf algebroids are, and how they’re analogous to groupoids.  I’ll build up to this slowly, though, without even giving the definition of Hopf algebroid at first.  Of course, if you’re eager to see it, you can always cheat and look up the definition here:

but I’ll warn you that the relationship to groupoids might not be obvious at first.  At least, it wasn’t to me.  In fact, going from Hopf algebras to Hopf algebroids took considerable work, and some time to settle on the correct definition. But the definition of Hopf algebroid given here in Böhm’s paper seems to be the one left standing after the dust settled.  This review article also includes a brief summary of the development of the subject.

To work up to Hopf algebroids, I’ll start with something simpler: weak Hopf algebras. These are a rather mild generalization of Hopf algebras, and the definition doesn’t look immediately “oid”-ish. But in fact, they are a nice compromise between between Hopf algebras and Hopf algebroids.  In particular, as we’ll see, just as a group has a Hopf algebra structure on its groupoid algebra, a groupoid has a weak Hopf algebra structure on its groupoid algebra.

Better yet, any weak Hopf algebra can be turned into a Hopf algebroid, and Hopf algebroids built in this way are rich enough to see many of features of general Hopf algebroids. So, I think this gives a pretty good way to understand Hopf algebroids, which might otherwise seem obscure at first. The strategy will be to start with weak Hopf algebras and consider what “groupoid-like” structure is already present. In fact, to emphasize how well they parallel ordinary groupoids, weak Hopf algebras are sometimes called quantum groupoids:

So, here we go…

What is a Weak Hopf algebra?  This is quick to define using string diagrams.  First, let’s define a weak bialgebra.  Just like a bialgebra, a weak bialgebra is both an associative algebra with unit:

and a coassociative coalgebra with counit:

(If the meaning of these diagrams isn’t clear, you can learn about string diagrams in several places on the web, like here or here.)

Compatibility of multiplication and comultiplication is also just like in an ordinary bialgebra or Hopf algebra:

So the only place where the axioms of a weak bialgebra are “weak” is in the compatibility between unit and comultiplication and between counit and multiplication.  If we define these combinations:

then the remaining axioms of a weak bialgebra can be drawn like this:

The two middle pictures in these equations have not quite been defined yet, but I hope it’s clear what they mean. For example, the diagram in the middle on the top row means either of these:

since these are the same by associativity.

Just as a Hopf algebra is a bialgebra with an antipode, a weak Hopf algebra is a weak bialgebra with an antipode.  The antipode is a linear involution $S$ which I’ll draw like this:

and it satisfies these axioms:

Like in a Hopf algebra, having an antipode isn’t additional structure on a weak Hopf algebra, but just a property: a weak bialgebra either has an antipode or it doesn’t, and if it does, the antipode is unique.  The antipode also has most of the properties you would expect from Hopf algebra theory.

One thing to notice is that the equations defining a weak Hopf algebra are completely self-dual.  This is easy to see from the diagrammatic definition given here, where duality corresponds to a rotation of 180 degrees: rotate all of the defining diagrams and you get the same diagrams back.  Luckily, even the letter $S$ is self-dual.

There’s plenty to say about about weak Hopf algebras themselves, but here I want to concentrate on how they are related to groupoids, and ultimately how they give examples of Hopf algebroids.

To see the “groupoidiness” of weak Hopf algebras, it helps to start at the bottom: the antipode axioms.  In particular, look at this one:

The left side instructs us to duplicate an element, apply the antipode to the copy on the right, and then multiply the two copies together.  If we do this to an element of a group, where the antipode is the inversion map, we get the identity.  If we do it to a morphism in a groupoid, we get the identity on the target of that morphism. So, in the groupoid world, the left side of this equation is the same as applying the target map, and then turning this back into a morphism by using the map that sends any object to its identity morphism.  That is:

$g \mapsto 1_{t(g)}$

where $t$ is the map sending each morphism to its target, and $1_x$ denotes the identity morphism on the object $x$.

Likewise, consider the dual of the previous axiom:

In the groupoid world, the left hand side gives the map

$g \mapsto 1_{s(g)}$

where $s$ denotes the map sending each morphism to its source.

So… if weak Hopf algebras really are like groupoids, then these two loop diagrams:

must essentially be graphical representations of the target and source maps.

Of course, I only said if Hopf algebras are like groupoids, and I haven’t yet explained any precise sense in which they are.   But we’re getting there.  Next time, I’ll explain more, including how groupoid algebras give weak Hopf algebras.

Meanwhile, if you want some fun with string diagrams, think of other things that are true for groupoids, and see if you can show weak Hopf algebra analogs of them using just diagrams.  For example, you can check that the diagrammatic analog of $1_{s(1_{s(g)})}=1_{s(g)}$ (“the source of the source is the source”) follows from the weak Hopf algebra axioms.  Some others hold make a trivial rephrasing: while the obvious diagrammatic translation of $1_{t(S(g))} = 1_{s(g)}$ does not hold,  if you draw it instead starting from the equation $1_{t(S(g))} = S(1_{s(g)})$, then you get an equation that holds in any weak Hopf algebra.

## Blog post on Observer Space by Jeffrey Morton

17 October 2012

DW: This is a very nice blog post by Jeffrey Morton about observer space! He wrote this based on my ILQGS talk and my papers with Steffen Gielen. (In fact, Jeff has written a lot of other nice summaries of papers and talks, as well as stuff about his own research, on his blog, Theoretical Atlas — check it out!)

This entry is a by-special-request blog, which Derek Wise invited me to write for the blog associated with the International Loop Quantum Gravity Seminar, and it will appear over there as well.  The ILQGS is a long-running regular seminar which runs as a teleconference, with people joining in from various countries, on various topics which are more or less closely related to Loop Quantum Gravity and the interests of people who work on it.  The custom is that when someone gives a talk, someone else writes up a description of the talk for the ILQGS blog, and Derek invited me to write up a description of his talk.  The audio file of the talk itself is available in .aiff and .wav formats, and the slides are here.

The talk that Derek gave was based on a project of his and Steffen Gielen’s, which has taken written form in a…

View original post 2,961 more words

## Observer Space: new paper and ILQGS talk

3 October 2012

Steffen Gielen and I just put our new paper on “observer space” on the arxiv:

S. Gielen and D. Wise, Lifting General Relativity to Observer Space

Then, today I gave the International Loop Quantum Gravity Seminar on the same topic. This a seminar between various institutions, mainly in North America and Europe, where people work on loop quantum gravity and related topics. It’s run the old-fashioned way, as a conference call.

I was a bit uneasy about volunteering for such a talk. I don’t like phones. I’m happy to speak in front of any audience I can see — but an audience I can’t see is a little intimidating, even if I do probably know most of them. Besides, on the phone, you never know whether someone might be recording your conversation, hoping to use it against you later. And in this case, they were! Here’s the audio to my talk in aiff or wav format. If you decide to listen to that, you might also want to look at the slides to my talk.

Seriously, I think the talk turned out rather well — except for the part where my Skype connection to the phone bridge cut out, and I didn’t even know it. Fortunately, though, as I only found out after the talk, Steffen took over, explaining to the audience the same stuff that I was simultaneously, unwittingly, explaining into a black hole. Steffen had never seen the slides, and described this as his first experience with live Powerpoint karaoke. I think he did an excellent job of filling in.

I’ll have to explain a bit more about “observer space” on this blog sometime later…


text:
## A geometric method for the approximation by nearest integer continued fractions. (Eine geometrische Methode bei der Approximation durch Kettenbrüche nach dem nächsten Ganzen.)(German)Zbl 0837.11003

Let $$A_n/B_n$$ be the convergents in the nearest integer continued fraction expansion for some real irrational number $$a$$, and define $$\lambda_n$$ by $$|a - A_n/B_n |= 1/(\lambda_n B^2_n)$$. H. Jager and C. Kraaikamp [Indag. Math. 51, 289-307 (1989; Zbl 0695.10029)] developed a geometric method to show that $$\max (\lambda_{n - 1}, \lambda_n, \lambda_{n + 1}) > (11 + 5 \sqrt 5)/10$$, for any $$n$$. The lower bound falls short of Borel’s bound $$\sqrt 5$$ in an analogous estimate for simple continued fraction approximations.
The authors use the method to show that the lower bound is best possible, and that Borel’s bound cannot be achieved by increasing the number of consecutive convergents. This has also been proved by J. Tong [Math. Scand. 71, 161-166 (1992; Zbl 0787.11028)] by another method.

### MSC:

 11A55 Continued fractions 11J70 Continued fractions and generalizations

### Citations:

Zbl 0695.10029; Zbl 0787.11028
Full Text:

format: plain


text:
# Suffix arrays: How to compute them fast with Python¶

By Louis Abraham

You can download the notebook from https://louisabraham.github.io/notebooks/suffix_arrays.ipynb

You can comment there on HN. Yes, I'm using HN as a comment system.

# Just give me the code!¶

In [1]:
from itertools import zip_longest, islice

def to_int_keys_best(l):
"""
l: iterable of keys
returns: a list with integer keys
"""
seen = set()
ls = []
for e in l:
if not e in seen:
ls.append(e)
ls.sort()
index = {v: i for i, v in enumerate(ls)}
return [index[v] for v in l]

def suffix_matrix_best(s):
"""
suffix matrix of s
O(n * log(n)^2)
"""
n = len(s)
k = 1
line = to_int_keys_best(s)
ans = [line]
while max(line) < n - 1:
line = to_int_keys_best(
[a * (n + 1) + b + 1
for (a, b) in
zip_longest(line, islice(line, k, None),
fillvalue=-1)])
ans.append(line)
k <<= 1
return ans

def suffix_array_best(s):
"""
suffix array of s
O(n * log(n)^2)
"""
n = len(s)
k = 1
line = to_int_keys_best(s)
while max(line) < n - 1:
line = to_int_keys_best(
[a * (n + 1) + b + 1
for (a, b) in
zip_longest(line, islice(line, k, None),
fillvalue=-1)])
k <<= 1
return line

# Disclaimer¶

This notebook is not intended as a course, a tutorial or an explanation on the suffix array algorithms, just practical implementations in Python.

This implementation is intended to be simple enough to be rewritten during programming contests, and yet be as efficient as possible. It is particularly optimised against random data.

# Introduction¶

This week-end, I wanted to improve my skills on string algorithms and solve this kattis problem. I had an efficient (in complexity) algorithm to compute the suffix array but it hit the time limit (mostly because I'm using Python). When I implemented my last line skipping trick, my code passed with Python 2 because the server uses PyPy. However, I still had a timeout in Python 3. This is how I managed to have a fast solution with the CPython implementation of Python 3.

I had a couple resources on the topic, so I started with [Stanford].

This paper is really the best I know because out of 17 pages, there are 7 of theory and code, and 9 of exercises with solutions (last page is for references).

They use an algorithm called prefix doubling, and I'm going to describe some possible implementations and their practical performances.

# Short reminder¶

## Suffix array¶

Given a string s of length n, we want to compute the suffix array sa of same length.

sa[i] is the rank according to the lexicographic order of the suffix at index i s[i:] amongst all the suffixes.

They are strictly ordered (two suffixes cannot be equal since they are all of different lengths) thus the suffix array is always a permutation of range(n).

For example, the suffix array of 'banana' is [3, 2, 5, 1, 4, 0]. We can see that the first two suffixes (ranks 0 and 1) are the ones that begin with the letter 'a'.

There is an equivalent definition of suffix arrays: sa_alternative[i] is the index of the suffix at the i-th position in the sorted list of all suffixes.

In [2]:
def suffix_array_alternative_naive(s):
return [rank for suffix, rank in sorted((s[i:], i) for i in range(len(s)))]

suffix_array_alternative_naive('banana')

Out[2]:
[5, 3, 1, 0, 4, 2]

As you can see, this is exactly the inverse permutation of sa, and it is trivial to invert it in $O(n)$.

In [3]:
def inverse_array(l):
n = len(l)
ans = [0] * n
for i in range(n):
ans[l[i]] = i
return ans

def suffix_array_naive(s):
return inverse_array(suffix_array_alternative_naive(s))

suffix_array_naive('banana')

Out[3]:
[3, 2, 5, 1, 4, 0]

Now the performance doesn't seem horrible:

In [4]:
from random import randint

constant_string = lambda length: 'a' * int(length)
random_string = lambda length: ''.join(chr(randint(ord('a'), ord('z')))
for _ in range(int(length)))

s1 = constant_string(1e4)
s2 = random_string(1e4)

%timeit suffix_array_alternative_naive(s1)
%timeit suffix_array_alternative_naive(s2)

10 loops, best of 3: 37 ms per loop
10 loops, best of 3: 46.6 ms per loop

The time complexity is dominated by the generation of sorted((s[i:], i) for i in range(len(s))) which is $O(n^2log(n))$ in the worst case: $O(n*log(n))$ for the sort and $O(n)$ for one comparison.

In practice, it is not really bad because the strings start to be different really quickly, so the $O(n)$ factor becomes less significant.

But the worst is the memory cost $O(n^2)$. That makes the algorithm for length = 100000 use several Go of RAM.

Because string comparisons seem to be really optimised in Python, the trivial algorithm slightly outperforms the more efficient algorithms for the small values. However, it is really not usable for bigger values of n.

Here, one could think that the performance could be worse for the constant_string because of the comparisons. However, because the prefixes are already sorted and the constant behind the string comparison is really small, it appears faster. See my question on [StackOverflow].

### One exercise for the reader¶

The constant_string is such that the number of letter comparisons between two suffixes is maximal (always the length of the longest). Find an algorithm to produce given an alphabet $A$ and a length $n$ an element of $A^n$ such that the maximum number of comparisons between any two suffixes is minimal.

You can find the solution here.

## Prefix doubling¶

The algorithm described in [Stanford] is called prefix doubling.

Let's say all the letters of your string are different. Then the order of the suffixes is only determined by their first letter, and you can do that in $O(n*log(n))$ time and $O(n)$ space complexity by sorting the letters.

Even if the letters are not different, grouping the suffixes according to their first letter is a good idea. It is the idea of prefix radix sort.

And here we can use an idea similar to pointer jumping to double at each step the length of the prefixes that are compared.

Say you have at step log(k) the orders of the partial prefixes s[i: i+k]. But s[i: i+2*k] == s[i: i+k] + s[i+k: 2*k] so you can merge at each step the order and the shifted order to obtain the new order. Hence the name prefix doubling. It is really a beautiful algorithm.

After at most $log(n)$ steps, you have totally sorted the prefixes. The complexity is $O(n)$ space (or $O(n*log(n))$ for the prefix matrix, see below) and $O(n*log^2n)$ time if you implement the merge operation in $O(n*log(n))$.

## Prefix matrix¶

When you use prefix doubling, keeping the intermediate partial sorts allows us to compute the Longest Common Prefix (LCP) of two indexes i and j in $O(log(n))$. The strategy is described in [Stanford].

This is the reason why I prefer prefix doubling over others because it is a semilinear computation to make LCP queries in $O(log(n))$ time. If you think thoroughly, using the suffix matrix to compute the LCP is similar to the father pointer doubling algorithm for Lowest Common Ancestor (LCA) in the suffix tree, see [Topcoder].

## Other algorithms¶

There are $O(n)$ algorithms to compute the suffix array, like building the suffix tree and converting it to suffix array, but the constant is high. A more efficient algorithms is the Skew algorithms: [Skew].

However, the Skew algorithm does not allow simple computation of the LCA.

I think there are more complicated algorithms using both the suffix array and the LCP array to be able to traverse the suffix tree without constructing it, and then you can use other classic algorithms for the LCA.

# The basic implementation¶

In [5]:
from itertools import zip_longest, islice

def to_int_keys(l):
"""
l: iterable of keys
returns: a list with integer keys
"""
index = {v: i for i, v in enumerate(sorted(set(l)))}
return [index[v] for v in l]

def suffix_matrix(to_int_keys, s):
n = len(s)
k = 1
line = to_int_keys(s)
ans = [line]
while k < n:
line = to_int_keys(
list(zip_longest(line, islice(line, k, None),
fillvalue=-1)))
ans.append(line)
k <<= 1
return ans

suffix_matrix(to_int_keys, 'banana')

Out[5]:
[[1, 0, 2, 0, 2, 0],
[2, 1, 3, 1, 3, 0],
[3, 2, 5, 1, 4, 0],
[3, 2, 5, 1, 4, 0]]

The to_int_keys function contains almost all the magic. It takes any iterable and returns integer indexes. If two elements were identical, their indexes will be equal.

Using positive integers allows us to set $-1$ as the smallest possible value.

## The original implementation¶

I wrote a version almost identical to the C++ code of the pdf, but it has bad performances.

In [6]:
def suffix_matrix_stanford(s):
n = len(s)
k = 1
line = to_int_keys(s)
ans = [line]
while k < n:
L = sorted(
(key, index)
for index, key in enumerate(
zip_longest(line, islice(line, k, None),
fillvalue=-1)
))
line = [0] * n
for i in range(n):
line[L[i][1]] = (line[L[i - 1][1]]
if i and L[i][0] == L[i - 1][0]
else i)
ans.append(line)
k <<= 1
return ans

suffix_matrix_stanford('banana')

Out[6]:
[[1, 0, 2, 0, 2, 0],
[3, 1, 4, 1, 4, 0],
[3, 2, 5, 1, 4, 0],
[3, 2, 5, 1, 4, 0]]

You can see the indexes are different in some lines of the matrix but they are in the same order, which is sufficient.

In [7]:
for s in [constant_string(1e5),
random_string(1e5)]:
%timeit suffix_matrix(to_int_keys, s)
%timeit suffix_matrix_stanford(s)

1 loop, best of 3: 1.06 s per loop
1 loop, best of 3: 1.72 s per loop
1 loop, best of 3: 4.29 s per loop
1 loop, best of 3: 7.14 s per loop

It shows that the Python builtins are very powerful.

We can however observe that using set might slow down sorted because Timsort performs well with partially sorted data, and sets are not ordered in Python. Can we fix that?

## Small tricks¶

### An optimisation based on Timsort¶

After a few steps, the array is almost sorted and the Timsort performs well on that data. In the random case, the suffix is computed after a few steps, and sorting is done in $O(n)$ because the Timsort is adaptative (and in general is "designed to perform well on many kinds of real-world data").

We test different to_int_keys functions implementing this trick:

In [8]:
def to_int_keys1(l):
"""
l: iterable of keys
returns: a list with integer keys
"""
ls = []
for e in sorted(l):
if not ls or e != ls[-1]:
ls.append(e)
index = {v: i for i, v in enumerate(ls)}
return [index[v] for v in l]

def to_int_keys2(l):
"""
l: iterable of keys
returns: a list with integer keys
"""
cnt = 0
lastKey = None
index = {}
for key in sorted(l):
if key != lastKey:
index[key] = cnt
cnt += 1
lastKey = key
return [index[v] for v in l]

def to_int_keys3(l):
"""
l: iterable of keys
returns: a list with integer keys
"""
seen = set()
ls = []
for e in l:
if not e in seen:
ls.append(e)
ls.sort()
index = {v: i for i, v in enumerate(ls)}
return [index[v] for v in l]

### Faster sorting using integers¶

We can do a little hack to compare integers of range(n * (n + 1)) instead of tuples.

In [9]:
def suffix_matrix_int(to_int_keys, s):
n = len(s)
k = 1
line = to_int_keys(s)
ans = [line]
while k < n:
line = to_int_keys(
[a * (n + 1) + b + 1
for (a, b) in
zip_longest(line, islice(line, k, None),
fillvalue=-1)])
ans.append(line)
k <<= 1
return ans

## Performance test¶

Now, let's compare everybody:

In [10]:
for length in [1e4, 1e5, 5e5]:
print("length = %i\n" % length)
for s in ['constant_string',
'random_string']:
print(s)
s = eval(s)(length)
for sm in ['suffix_matrix', 'suffix_matrix_int']:
print(sm)
sm = eval(sm)
%timeit sm(to_int_keys, s)
%timeit sm(to_int_keys1, s)
%timeit sm(to_int_keys2, s)
%timeit sm(to_int_keys3, s)
print()

length = 10000

constant_string
suffix_matrix
10 loops, best of 3: 53.3 ms per loop
10 loops, best of 3: 48.3 ms per loop
10 loops, best of 3: 65 ms per loop
10 loops, best of 3: 48.2 ms per loop

suffix_matrix_int
10 loops, best of 3: 59.8 ms per loop
10 loops, best of 3: 77.3 ms per loop
10 loops, best of 3: 59.4 ms per loop
10 loops, best of 3: 63.9 ms per loop

random_string
suffix_matrix
10 loops, best of 3: 188 ms per loop
1 loop, best of 3: 233 ms per loop
1 loop, best of 3: 197 ms per loop
1 loop, best of 3: 212 ms per loop

suffix_matrix_int
1 loop, best of 3: 193 ms per loop
1 loop, best of 3: 185 ms per loop
10 loops, best of 3: 132 ms per loop
1 loop, best of 3: 169 ms per loop

length = 100000

constant_string
suffix_matrix
1 loop, best of 3: 829 ms per loop
1 loop, best of 3: 665 ms per loop
1 loop, best of 3: 583 ms per loop
1 loop, best of 3: 633 ms per loop

suffix_matrix_int
1 loop, best of 3: 857 ms per loop
1 loop, best of 3: 861 ms per loop
1 loop, best of 3: 846 ms per loop
1 loop, best of 3: 776 ms per loop

random_string
suffix_matrix
1 loop, best of 3: 4.57 s per loop
1 loop, best of 3: 4.16 s per loop
1 loop, best of 3: 3.87 s per loop
1 loop, best of 3: 4.7 s per loop

suffix_matrix_int
1 loop, best of 3: 2.93 s per loop
1 loop, best of 3: 2.98 s per loop
1 loop, best of 3: 2.82 s per loop
1 loop, best of 3: 3.34 s per loop

length = 500000

constant_string
suffix_matrix
1 loop, best of 3: 5.06 s per loop
1 loop, best of 3: 4.42 s per loop
1 loop, best of 3: 3.97 s per loop
1 loop, best of 3: 4.15 s per loop

suffix_matrix_int
1 loop, best of 3: 4.89 s per loop
1 loop, best of 3: 5.16 s per loop
1 loop, best of 3: 4.7 s per loop
1 loop, best of 3: 5.9 s per loop

random_string
suffix_matrix
1 loop, best of 3: 34.9 s per loop
1 loop, best of 3: 32.3 s per loop
1 loop, best of 3: 30.8 s per loop
1 loop, best of 3: 35.8 s per loop

suffix_matrix_int
1 loop, best of 3: 25.5 s per loop
1 loop, best of 3: 24.2 s per loop
1 loop, best of 3: 21.5 s per loop
1 loop, best of 3: 26.3 s per loop

Using integer keys helps speeding up the computations for random_string, slowing them a bit for the constant_string.

We can see that the three new functions perform very well, and the big winner is to_int_keys2.

The performance gained from applying the Timsort on partially sorted data is too complicated to be evaluated, it is only a rule of thumb that performs very well.

I was expecting to_int_keys3 to perform better because there is some kind of "equilibrium" between the number of different elements to sort and their partial order.

Indeed, to_int_keys3 has a $O(A*log(A) + n)$ time complexity where A is the number of different elements, so it should be faster on the first steps when the alphabet is small. However, the online operations done on set seem to be inefficient so the difference can only be seen on large values.

We can also observe that using suffix_matrix_int helps to_int_keys3, probably because set is more efficient with integers than with tuples.

# Interlude: an outsider¶

On [AlgorithmicAlley], I found a surprisingly elegant algorithm (I modified it a bit):

In [11]:
from collections import defaultdict

def sort_bucket(s, bucket, order):
d = defaultdict(list)
for i in bucket:
key = s[i + order // 2:i + order]
d[key].append(i)
result = []
for k, v in sorted(d.items()):
if len(v) > 1:
result += sort_bucket(s, v, 2 * order)
else:
result.append(v[0])
return result

def suffix_array_ManberMyers(s):
return sort_bucket(s, range(len(s)), 1)

suffix_array_ManberMyers('banana')

Out[11]:
[5, 3, 1, 0, 4, 2]
In [12]:
s = random_string(1e5)

%timeit suffix_matrix_int(to_int_keys2, s)
%timeit suffix_array_ManberMyers(s)

1 loop, best of 3: 2.87 s per loop
1 loop, best of 3: 334 ms per loop

Yes, almost 10 times better. At first, I was impressed. Then I tested it on a constant example:

In [13]:
s = constant_string(5e4)

%timeit suffix_array_naive(s)
%timeit suffix_matrix(to_int_keys2, s)
%timeit suffix_array_ManberMyers(s)

1 loop, best of 3: 1.03 s per loop
1 loop, best of 3: 286 ms per loop
1 loop, best of 3: 2.04 s per loop

What happened?

When d.items() is sorted, it contains the real substrings. When you don't need to go really deep (like with a random string), it's not a problem. Because you don't compute the orders that are not useful, you limit the number of comparisons and you spare a lot of time. But the principle of prefix doubling is precisely to use the partial order that is already computed.

In fact, for constant_string, you have to store almost all the suffixes before sorting them, and because you use a defaultdict, it is even less space and time efficient than the naive algorithm, and is $O(n^2)$.

So this implementation is really not the same algorithm. And because of the method used, you don't have the suffix matrix that justifies to use a $O(n*log^2n)$ algorithm instead of the linear [Skew].

# Awesome optimisation: skipping the last lines¶

## The idea¶

We saw that when the suffixes can be compared fast, there are a lot of neat optimisations, either by exploiting the Timsort or by comparing the string themselves like in [AlgorithmicAlley].

We can observe that if it is the case, the last lines of the matrix are going to be the same. Then, we don't need them!

The stop condition is simply to check if we have all the integers. We only change one line.

For random strings, the mean time to compare two prefixes is $O(log(n))$ instead of $O(n)$ so we do only about $O(log(log(n)))$ steps instead of $O(log(n))$.

I have never seen this trick anywhere, if you know a reference, please tell me on HN!

In [14]:
def suffix_matrix_smart(to_int_keys, s):
n = len(s)
k = 1
line = to_int_keys(s)
ans = [line]
while max(line) < n - 1:
line = to_int_keys(
list(zip_longest(line, islice(line, k, None),
fillvalue=-1)))
ans.append(line)
k <<= 1
return ans

suffix_matrix_smart(to_int_keys2, 'banana')

Out[14]:
[[1, 0, 2, 0, 2, 0], [2, 1, 3, 1, 3, 0], [3, 2, 5, 1, 4, 0]]
In [15]:
for s in [constant_string(1e5), random_string(1e5)]:
%timeit suffix_matrix(to_int_keys2, s)
%timeit suffix_matrix_smart(to_int_keys2, s)

1 loop, best of 3: 704 ms per loop
1 loop, best of 3: 747 ms per loop
1 loop, best of 3: 4.35 s per loop
1 loop, best of 3: 639 ms per loop

That's really better for the random_string.

The reason is that we don't compute the last lines that are identical.

In [16]:
s = random_string(1e5)
sm = suffix_matrix(to_int_keys2, s)
sms = suffix_matrix_smart(to_int_keys2, s)

print(len(sm), len(sms))
print(sm[:len(sms)] == sms)

18 4
True

## It is even better with integers¶

Let's test again the performances with integers:

In [17]:
def suffix_matrix_smart_int(to_int_keys, s):
"""
suffix matrix of s
O(n * log(n)^2)
"""
n = len(s)
k = 1
line = to_int_keys(s)
ans = [line]
while max(line) < n - 1:
line = to_int_keys(
[a * (n + 1) + b + 1
for (a, b) in
zip_longest(line, islice(line, k, None),
fillvalue=-1)])
ans.append(line)
k <<= 1
return ans

In [18]:
for length in [1e5, 5e5]:
print("length = %i\n" % length)
for s in ['constant_string',
'random_string']:
print(s)
s = eval(s)(length)
for sm in ['suffix_matrix_smart',
'suffix_matrix_smart_int']:
print(sm)
sm = eval(sm)
%timeit sm(to_int_keys2, s)
%timeit sm(to_int_keys3, s)
print()

length = 100000

constant_string
suffix_matrix_smart
1 loop, best of 3: 761 ms per loop
1 loop, best of 3: 837 ms per loop

suffix_matrix_smart_int
1 loop, best of 3: 954 ms per loop
1 loop, best of 3: 967 ms per loop

random_string
suffix_matrix_smart
1 loop, best of 3: 618 ms per loop
1 loop, best of 3: 645 ms per loop

suffix_matrix_smart_int
1 loop, best of 3: 529 ms per loop
1 loop, best of 3: 536 ms per loop

length = 500000

constant_string
suffix_matrix_smart
1 loop, best of 3: 5.4 s per loop
1 loop, best of 3: 4.33 s per loop

suffix_matrix_smart_int
1 loop, best of 3: 5.5 s per loop
1 loop, best of 3: 5.49 s per loop

random_string
suffix_matrix_smart
1 loop, best of 3: 3.93 s per loop
1 loop, best of 3: 3.74 s per loop

suffix_matrix_smart_int
1 loop, best of 3: 2.9 s per loop
1 loop, best of 3: 2.45 s per loop

As I explained before, to_int_keys3 is really better for the first steps (and when we work with integers). Since we are stopping after less steps, to_int_keys3 provides the best results.

The to_int_keys_best, suffix_matrix_best and suffix_array_best functions of the beginning are just some refactoring of to_int_keys3 and suffix_matrix_smart_int.

## Final remarks on the LCP computation¶

Discarding the last identical lines of the suffix matrix is not a problem to compute the LCP:

In [19]:
def lcp(sm, i, j):
"""
longest common prefix
O(log(n))

sm: suffix matrix
"""
n = len(sm[-1])
if i == j:
return n - i
k = 1 << (len(sm) - 2)
ans = 0
for line in sm[-2::-1]:
if i >= n or j >= n:
break
if line[i] == line[j]:
ans ^= k
i += k
j += k
k >>= 1
return ans

print(lcp(suffix_matrix(to_int_keys, 'banana'), 2, 4))
print(lcp(suffix_matrix_smart(to_int_keys, 'banana'), 2, 4))

2
2

# Plus Ultra¶

The prefix doubling algorithm uses $O(log(n))$ steps that cost each $O(n*log(n))$ (or $O(A*log(A) + n)$ with to_int_keys3).

We attacked the first $O(log(n))$ factor for random strings.

Now, if you use a radix sort, you can implement to_int_key in $O(n)$, and use it with suffix_matrix_smart or suffix_matrix_smart_int (the former seems more suitable to avoid moduli operations).

I implemented a radix sort based to_int_keys function that was not optimised and used it with suffix_matrix_smart. I tested it against suffix_matrix_best and it had similar results against random_string but performed really bad against constant_string. My radix sort was not optimised for almost sorted arrays, and was quite bad because it was not in place and had to reduce two elements counting arrays (see below).

In fact, the native Timsort is so efficient that it beats the radix sort when we provide almost sorted arrays. I don't know what would happen for really high values of $n$ (tested up to 5e6), but who would process longer arrays on a single computer with a Python code?

You can consult those two good references:


text:
Piptobak sha - piptobak är lite finare tobak avsedd för pipor

Multiple variants of the … Easily calculate CRC32 checksum and find related resources. Easy to use online CRC-32 checksum calculator. CRC-32 Checksum Calculator (Hash Generator) Learn about CRC-32 algorithm and easily calculate CRC-32 checksum of any The polynomial must be chosen to maximize the error-detecting capabilities while minimizing overall collision For a 1% probability of collision, you need 6.1 × 10^8 entries. For a 50% probability of collision, you need 5.1 × 10^9 entries. Of course, if the data is potentially supplied by malicious sources, then collisions in a hash as simple as crc64 can be generated easily, and collisions could be rampant.

Demonstrates how to calculate CRC32 checksums using the same method as WinZip. The CRC (Cyclic Redundancy Checksum) algorithm is a highly optimised and powerful way of checking whether a large number of bytes have been modified or not. 1 Tutorial: Checksum and CRC Data Integrity Techniques for Aviation May 9, 2012 Philip Koopman Carnegie Mellon University koopman@cmu.edu Co-PIs: Kevin Driscoll 2021-03-30 · Collision insurance helps pay to repair your car if it’s damaged in a wreck with another vehicle or object, such as a pole or a fence. It’s typically used when the damage is the result of PSoC® Creator™ Component Datasheet Cyclic Redundancy Check (CRC) Document Number: 002-20387 Rev. *A Page 3 of 19 Component Parameters Drag a CRC Component onto your design and double click it to open the Configure dialog. 2009-05-27 · You dont need the Hascode , to use the CRC32 Class, follow the steps below Crc32 crc32 = new Crc32(); String hash = String.Empty; Input data is the byte 0xC2 = b 11000010. As generator polynomial (=divisor), let's use b 100011101.

or at least, a CRC-32 collision sounds far more likely.

## Vi Ska Aldrig Bli Som Dom - Headons - Board index

Afterwards, the achieved knowledge is expanded to CRC-16 and CRC-32 calculation, The improvement of speed comes at the cost of processing time to The more bits the CRC value has the less is the probability of a collision: for CRC 1999-04-17 Vernon Schryver: "On the contrary, CRC-32 and other error In practice, the hash function had a collision rate of much better than 10e-6 messages. Problem arises when these hashing start causing collisions, There are various ways of resolving hash collision as mentioned in the Wikipedia article, but usage   12 Jun 2016 Hash functions also try to optimize to reduce hash collisions for differing the most widely used CRC that I've seen used is CRC-32 which has  No carrier sense and no collision detection.

### RS 485 CRC - LibStock

When a catalyst is involved in the collision between the reactant molecules, less energy is required for the chemical change to take place, and hence more collisions have sufficient energy for reaction to occur. The reaction rate therefore increases. CRC32 Hash Generator is a free online CRC-32 Encrypt Decrypt Tool.

The probability of at least one collision is about 1 - 3x10-51. The average number of collisions you would expect is about 116. In general, the average number of collisions in k samples, each a random choice among n possible values is: The probability of at least one A CRC-32 will always detect a single sequence of errors up to 32 bits. or at least, a CRC-32 collision sounds far more likely. Citrus538. Ars Legatus Legionis Registered: Jul 21, 2000 Take the well-known hash function CRC32, for example. If you feed this function the two strings “plumless” and “buckeroo”, it generates the same value.

https: There are two types of collision here. The first type is when two URLs map to the same CRC. To prevent that type of collision, CRC-64 is likely better than CRC-32. The second type of collision occurs when you try to map hash values into hash table indices. I don't know how you plan to map hash values to hash Instead of running the full SHA1/MD5 simultaneous collision attack $33$ times, we only run it once with an increased effort in steps 1 and 3. More precisely, using the value of $2^{63.1}$ SHA1 compressions from the SHAttered paper , we require the equivalent of $\approx 2^{69.7}$ SHA1 compressions in step 1, and $\approx 2^{70}$ MD5 compressions in step 3. 2020-08-17 · ; function input values: esi points to a 256 entry bit reflection table, aligned on a 256 byte boundary build_16b_crc_tbl: mov cx, 0xffff mov edi, Tbl_End ; store going down from Tbl_End. crc_tbll: mov ebx, esi xor eax, eax mov bl, cl mov al, [ebx]; bit-reflect the two input bytes mov bl, ch mov ah, [ebx] bswap eax; and then put them at upper end of register mov dl, 16; loop over all 16 bits This Video shows how easy to create a collision for a 5 character string.

and execute it; however the website only executes python files with a particular checksum value. Chances to get a collision this way are vanishingly small until you hash at least 2 n/2 messages, for a hash function with a n-bit output. This means that with any proper hash function with an output of 256 bits or more, the collision rate is, in practical conditions, zero (you will not get any and that's the end of the story). 2011-05-04 · This illustrates the probability of collision when using 32-bit hash values. It’s worth noting that a 50% chance of collision occurs when the number of hashes is 77163.
Honda bilmodeller 2021

The reaction rate therefore increases. CRC32 Hash Generator is a free online CRC-32 Encrypt Decrypt Tool. It converts any submitted text or value to the hash using CRC32 Algorithm. https: There are two types of collision here.

An increasing collision rate (number of packets output divided by the number of collisions) does not indicate a problem: it is merely an indication of a higher offered load to the network. An example of this could be because another station was added to the network. There is no set limit for "how many collisions are bad" or a maximum collision What is the Difference Between CRC-8, CRC-16, CRC-32 and CRC-64? The selection of the generator polynomial is the most important part of implementing the CRC algorithm. The polynomial must be chosen to maximize the error-detecting capabilities while minimizing overall collision probabilities. That'll give us a total of $2^{33}$ images with all the same MD5 and SHA-1 hash; there must be a pair of images with the same CRC-32 value as well, and so that solves the problem.
Christer zaar alla bolag

öhmans bygg stora höga
personbevis skattemyndigheten
jobba pa migrationsverket lon
farger og psykologi
när blir en demokrati en diktatur
fortal lag
stridsfordon 90 interiör

### From 70828de759d05ac06869aeb007ac6914edf3e382 Mon Sep

Tweet. Use this tool to generate Adler32, CRC-32, CRC-32b, Gost, HAVAL-128, HAVAL-160, Rate this converter. 5 Apr 2013 collision issues occur for very small block sizes, as the sum of A does not Figure 6: A comparison of CRC32 hashing rates for CPU and GPU. Results 1 - 16 of 125 It states to consider a collision for a hash function with a 256-bit output size or file using MD5, SHA1, SHA2, CRC32 and many other algorithms. FNV hashes are designed to be fast while maintaining a low coll 7 Apr 2016 This Video shows how easy to create a collision for a 5 character string. Puzzle source by alamarjan:  3 - Rate. If you look at two arbitrary values, the collision probability is only. 2^{\ frac{n}{2}} = 2^{-128} \text{(for 2 arbitrary value)}.

Kla sig
platsbanken pajala


text:
# How would one approach choosing 12 inputs to a formula, such that the square root of the output is a rational number?

I'm wondering how one would approach finding a combination of rational values for 12 variables $P_1,P_2,\cdots,P_{12}$, such that the square root of alpha, related to $P_1,\cdots,P_{12}$ by:

$\alpha= - \frac{P_3*P_7-P_1*P_5-P_2*P_6-P_4*P_8}{(P_3*P_{11}-P_1*P_9-P_2*P_{10}-P_4*P_{12})+(P_7*P_{11}-P_5*P_9-P_6*P_{10}-P_8*P_{12})}$

would be a rational number?

Incessant trial and error has always given an irrational answer. I can only think that $\alpha=-\frac{c^2}{d^2}$ for some integers $c, d$ for it to be a rational but that condition doesn't provide enough of a guideline.

Any suggestions greatly appreciated.

Solving for the numerator to be equal to $-c^2$ for some $c \in \mathbb{Q}$.

We get that $P_1=\frac{c^2-P_2 P_6+P_3 P_7-P_4 P_8}{P_5}$ assuming that $P_5 \not=0$.

Solving for the denominator to be equal to $d^2$ for some $d \in \mathbb{Q}$.

We get that $P_{12}=\frac{-d^2-P_1 P_9-P_{10} P_2-P_{10} P_6+P_{11} P_3+P_{11} P_7-P_5 P_9}{P_4+P_8}$ assuming $P_4+P_8 \not=0$.

thus we get that $\alpha = - \frac{-c^2}{d^2} = \frac{c^2}{d^2}$ and so $\sqrt{\alpha} = \frac{c}{d}$ assuming $d \not= 0$.

For instance :

$c=\frac{1}{2}$ and $P_2=\frac{1}{3} , P_3 = \frac{1}{4} , P_4 = \frac{2}{5} , P_5 = \frac{3}{7} , P_6 = \frac{2}{11} , P_7 = \frac{4}{9} , P_8 =\frac{1}{8}$ from these we can compute $P_1$ value which is $P_1 = \frac{868}{1485}$

Now $d=\frac{3}{2}$ and $P_9 = \frac{1485}{217} , P_{10} = \frac{7}{11} , P_{11}=\frac{1}{5}$ from these we can compute $P_{12}$ value which is $P_{12} = -\frac{620108920}{34738011}$

thus $\sqrt{\alpha} = \frac{c}{d} = \frac{\frac{1}{2}}{\frac{3}{2}} = \frac{1}{3}$

Now this guarantees that $\sqrt{\alpha} \in \mathbb{Q}$ but by far its not the only way, there is too many ways to ensure square root of $\alpha$ is rational because you have $14$ variables in one equation, meaning you have $13$ Degrees of freedom.

• What a fantastic answer thank you! It didn't even occur to me to equate the numerators and denominators separately! – Nyika Sep 9 '17 at 11:07
• @Nyika you are welcome (: – Ahmad Sep 9 '17 at 11:12


text:
Electrode control methodology for a scanning tunneling microscope
A control methodology for scanning tunneling microscopy is disclosed. Instead of utilizing Integral-based control systems, the methodology utilizes a dual-control algorithm to direct relative advancement of a STM tip towards a sample. A piezo actuator and stepper motor advances an STM tip towards a sample at a given distance until measuring a current greater than or equal to a desired setpoint current. Readings of the contemporaneous step are analyzed to direct the system to change continue or change direction and also determine the size of each step. In simulations where Proportion and/or Integral control methodology was added to the algorithm the stability of the feedback control is decreased. The present methodology accounts for temperature variances in the environment and also appears to clean and protect the tip electrode, prolonging its useful life.
Authors:
Award ID(s):
Publication Date:
NSF-PAR ID:
10066868
Journal Name:
U.S. patentSearch claims & abstracts
ISSN:
1069-3645


text:
# Help making a proof about a Lipschitz function rigorous

A function f:R→R is defined to be Lipschitz if there is a constant $K>0$ such that for all a,b∈R $|f(a)−f(b)|≤K|a−b$| (a) Use the mean value theorem to show that the function $f(x)=2sin(x)$ is Lipschitz.

(b) Suppose $f:R→R$ is Lipschitz. Prove that f is continuous. (Hints: Use squeeze law and/or the epsilon-delta definition of limit.

--My solution:

Part a:

$2sin(x)$ is continuous on $R$, in particular on $[b,a]$ and differentiable on $(b,a)$. By MVT, there exists $c∈(b,a)$ such that $$f′(c)= \frac{f(a)−f(b)}{a−b}$$ But $f′(x)=2cos(x)$, therefore $$f′(c)=2cos(c)$$ therefore $$2cos(c)= \frac{f(a)−f(b)}{a−b}$$ therefore

$$|2cos(c)|= \frac{|f(a)−f(b)|}{|a−b|}$$

but $|2cos(c)| ≤ 2$, therefore $$\frac{|f(a)−f(b)|}{|a−b|} ≤ 2$$

i.e. $$|f(a)-f(b)| ≤ 2|a-b|$$

Part b:

let $ϵ > 0$ and $x$, $x_0$ $∈ R$

for $f$ to be continuous at $x_0$, need to ensure that $|f(x) - f(x_0)| < ϵ$

now from part (a) we have: $$|f(x) - f(x_0)| ≤ K|x - x_0|$$

when $|x - x_0| < δ$ we have: $$|f(x) - f(x_0)| ≤ Kδ$$

let $δ = \frac{ϵ}{K}$

therefore we have: $$|f(x) - f(x_0)| < ϵ$$

therefore $f$ is continuous on $R$

Could someone please verify that this proof is rigorous enough and if not, point out where it needs to be adjusted. Thanks in advance!

-
Looks good to me, nice job. – Joseph G. May 12 '13 at 1:23


text:
<meta http-equiv="refresh" content="1; url=/nojavascript/">

# 4.6: Chapter 4 Review

Difficulty Level: At Grade Created by: Bruce DeWItt

This chapter covers the topics of data collection methods and potential sources of bias. We learned about experiments, observational studies, sample surveys and censuses. Several potential errors and sources or bias were introduced. We also learned how to use a random digit table to make random selections, how to outline experimental designs, and how to calculate and state 95% confidence intervals.

You should go back and read through each of the sections in this chapter, paying careful attention to all of the new terms in bold. This will help you to do problem 1 from your homework assignment.

### Chapter 4 Review Exercises

1) Study your new vocabulary!

a) If you have not already, make flashcards for the terms from this chapter. Write the term on one side of the card. On the other side, write a brief definition and include an example. Terms that appear in bold through section 4.1 through 4.5 are the new terms.

b) Study your flashcards.

2) Each statement below claims that the ACT’s are not a fair measurement for college readiness, but for a different reason. For each student's statement, determine whether he or she is questioning the validity, the reliability, or claiming that it will be biased. Explain your answers.

a) The ACT’s are not fair because it is timed and I cannot work fast enough. Consequently I am not really doing as well as I could; I always get a lower score than I should receive.

b) The ACT’s are not fair because the vocabulary is not clear and I do not even understand what the questions are asking me. I always study really hard and do my homework and I am totally ready for college, but that doesn't show up on some stupid test.

c) The ACT’s are not fair because the first time I took them I scored a 21, but the second time I scored a 16. How can that be right?

3) Suppose you want to take a simple random sample of 350 women, from a population of 4700 females on the University of Coolness campus.

a) Explain the steps you would follow if you were going to make the selection using a table of random digits (be thorough).

b) Starting at line 137, select the first five numbers.

4) Suppose that after carrying out your survey of 350 women, you found that 74 of the women said that they “did not feel safe walking on campus after dark”. Identify each of the following.

a) Population of interest

b) Parameter of interest

c) Sample

d) Statistic

e) Margin of error (quick method for 95%)

f) Calculate a 95% confidence interval

g) Make a 95% confidence statement

5) A high school social studies teacher wants to see if giving a completely multiple choice test versus a traditional free response test will improve student scores. She has designed two versions of the chapter 6 test to test her question. She has two classes – a 1st hour class with 32 students, and a 5th hour class with 37 students. The two classes are very different in both behavior and academic performance, so she decides to carry out her experiment using blocking. Identify the following:

a) Subjects

b) Explanatory variable(s)

c) Response variable

d) Will this experiment be blind? double-blind? placebo controlled?

e) Outline a randomized block experiment.

6) Suppose that you are trying to determine whether kindergarten students who have gone to child care centers show more aggressive behaviors than children who have not attended child care centers. You have the data regarding whether or not each child attended a child care center and for what length of time. You are now going to study aggressive behaviors. For each of the following, decide which type of data collection method is being proposed: observational study, sample survey, census, or experiment.

a) Observers will watch the kindergartners on the playground, recording aggressive behaviors.

b) A survey will be given to 20 randomly selected parents asking each to rate his or her child’s behavior.

c) A survey will be given to all kindergarten parents asking each to rate his or her child’s behavior.

d) During center time, a teacher will take a toy away from a child and record whether they act aggressively.

7) For the study in question 6

a) Suggest something that may go wrong with, or may be a source of bias, for each of the proposed data collection methods.

b) Which of the methods do you feel will yield the best results? Explain.

8) A researcher at the University of Minnesota believes that a certain component of ant venom can be used to lessen the amount of swelling in the knuckles of people suffering from arthritis. The ant venom treatment has been made into a capsule form that can be swallowed, and is designed to be taken one time per day. Suppose that you have 200 people suffering from arthritis who have volunteered to participate in this study. Identify the following:

a) Subjects

b) Explanatory variable

c) Response variable

d) Will this experiment be blind? double-blind? placebo controlled?

e) Outline a completely randomized design

9) Your teacher wants to find out whether chocolate helps students concentrate on their tests. In one class, she gives all of the students chocolate before the test begins. In another class, she does nothing. Is this an example of an observational study, a sample survey, a census, or an experiment? Give reasons to support your answer.

10) You bought a sweater on discount that was originally marked at $30. When you got to the register, it rung up as$23. What was the percent discount?

11) The cost of gas in 2001 was $1.45 per gallon. The average cost today is$3.75.

a) What is the amount of increase?

b) What is the percent of increase?

12) The table below shows the number of seniors and the number of seniors graduating for three high schools.

License: CC BY-NC 3.0

a) Which school has the most students graduating?

b) Determine the graduation rate for each school.

c) Which school has the highest graduation rate?

13) Identify the sampling method used in each of the following: SRS, stratified random sample, systematic random sample, multi-stage random sample, random cluster sample, voluntary response sample, convenience sample

a) Every fifth person boarding a plane is searched thoroughly.

b) At a local community College, five math classes are randomly selected out of 20 and all of the students from each class are interviewed.

c) A researcher randomly selects and interviews forty male and forty female teachers, from a university with 122 female and 135 male instructors.

d) A researcher for an airline interviews all of the passengers on five randomly selected flights.

e) Based on 12,500 responses from 42,000 surveys sent to its alumni, a major university estimated that the annual salary of its alumni was 92,500.

f) A community college student interviews everyone in his biology class to determine the percentage of students that own a car.

g) A market researcher randomly selects 200 drivers under 35 years of age and 100 drivers over 35 years of age, from those insured with Quality Car Insurance.

h) A researcher selects 12 states randomly. From each state, she randomly selects 20 middle schools. From each middle schools, she randomly selects 15 teachers. The 3,600 teachers were then interviewed by phone..

i) To avoid working late, the quality control manager inspects the last 10 items produced that day.

j) The names of 70 contestants are written on 70 cards. The cards are placed in a bag, and three names are picked from the bag.

14) The athletic director wants to know how tax payers in the community feel about funding for athletics at the high school. He surveys his coaches and the parents of athletes at his school. Describe what is wrong with his methodology.

15) Suppose that a poll was commissioned to determine whether people in the U.S. believe that pro wrestling is a sport. Identify the type(s) of bias that will likely be present in each of the following scenarios. Some will have more than one. Explain your answers.

a) An online poll was sent to all visitors of the WWE website.

b) Telephone interviews are done to randomly selected phone numbers between 4 p.m. and 8 p.m.

c) Some people were embarrassed to admit that they liked wrestling and think it is a sport.

d) One of the questions asked was, “Do you believe that the pro wrestlers are actors or should they be considered serious athletes?”

e) One of the researchers spilled coffee on a big stack of surveys and several had to be thrown away.

f) A second poll done had slightly different results.

g) WWE had fans fill out a survey as they left a pro wrestling event.

#### Image References:

Picture of cell phones. http://www.w-cellphones.com July 19, 2011.

Students measuring heights.http://t3.gstatic.com July 25, 2011.

Pop can. http://popartmachine.com July 25, 2011.

Calvin and Hobbes. http://www.stat.psu.edu/old_resources/Cartoons/cartoon014.gif July 27, 2011.

Clipboard. http://boylston.bbrsd.schoolfusion.us July 25, 2011.

Hockey Players.http://images.paraorkut.com July 25, 2011.

Scientist:http://www.reversingibs.com July 15, 2011.

1. [1]^ License: CC BY-NC 3.0

Jun 14, 2011


text:
Maximum principle for weak solutions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T03:13:46Z http://mathoverflow.net/feeds/question/61044 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61044/maximum-principle-for-weak-solutions Maximum principle for weak solutions Marc 2011-04-08T10:36:28Z 2011-04-08T11:49:57Z
Hello,

maximum principles for parabolic PDEs seem to be well-known, if the solution is a priori C^2 (cf. Protter, Weinberger: Maximum principles in differential equations). However, what about weak solutions? To be specific, are there any maximum principles on the nonnegativity of solutions $u\in W^{1,p}(0,T;L^p(\Omega))\cap L^p(0,T;W^{2,p}(\Omega))$, $p\in(1,\infty)$, where $\Omega\subset R^n$ is a bounded domain? For given nonnegative initial data, does the solution remain positive, as long as it exists?

I assume yes, since there are numerous authors that use the results from Weinberger/Protter just for weak solutions. I would appreciate any hints on this topic.

Best regards, Marc
 http://mathoverflow.net/questions/61044/maximum-principle-for-weak-solutions/61047#61047 Answer by András Bátkai for Maximum principle for weak solutions András Bátkai 2011-04-08T11:05:37Z 2011-04-08T11:05:37Z
Yes. If you use operaor semigroups to represent the solutions, you can infer the positivity of the mild solutions (which are the same as the weak solutions) immediately.

There is an extensive treatment of positive semigroups in R. nagel (ed.): One-parameter semigroups of positive operators, Springer, 1986.

You can find a nice introduction, with a short discussion of this topic in Engel-Nagel: A short course on operator semigroups, Springer, 2006. ChapterVI.

Of course, there are less functional analytic arguments as well, but this is what I am familiar with
 http://mathoverflow.net/questions/61044/maximum-principle-for-weak-solutions/61052#61052 Answer by Hans Engler for Maximum principle for weak solutions Hans Engler 2011-04-08T11:49:57Z 2011-04-08T11:49:57Z
You might want to distinguish between maximum principles (which assert typically things like "the max of the solution is attained on the boundary / parabolic boundary of the set") and positivity, which assert things like "if the data are non-negative on the (parabolic) boundary, then so is the solution in the entire domain". The latter often can be shown with functional analytic techniques (see previous post).

As to maximum principles for generalized solutions, there is work by Jensen on viscosity solutions of fully nonlinear elliptic problems. And there is work in the 70s that extends maximum principles for elliptic equations to solutions in $W^{2,n}$ where $n$ is the spatial dimension (if I remember correctly).


text:
# The Cauchy Transform

###### Joseph A. Cima, Alec L. Matheson, and William T. Ross
Publisher:
American Mathematical Society
Publication Date:
2006
Number of Pages:
272
Format:
Hardcover
Series:
Mathematical Surveys and Monographs 125
Price:
75.00
ISBN:
0821838717
Category:
Monograph
We do not plan to review this book.

Preface ix

Overview 1

Chapter 1. Preliminaries 11

1.1. Basic notation 11

1.2. Lebesgue spaces 11

1.3. Borel measures 14

1.4. Some elementary functional analysis 17

1.5. Some operator theory 20

1.6. Functional analysis on the space of measures 22

1.7. Non-tangential limits and angular derivatives 25

1.8. Poisson and conjugate Poisson integrals 30

1.9. The classical Hardy spaces 32

1.10. Weak-type spaces 35

1.11. Interpolation and Carleson’s theorem 36

1.12. Some integral estimates 39

Chapter 2. The Cauchy transform as a function 41

2.1. General properties of Cauchy integrals 41

2.2. Cauchy integrals and H1 46

2.3. Cauchy A-integrals 48

2.4. Fatou’s jump theorem 54

2.5. Plemelj’s formula 56

2.6. Tangential boundary behavior 58

2.7. Cauchy-Stieltjes integrals 59

Chapter 3. The Cauchy transform as an operator 61

3.1. An early theorem of Privalov 62

3.2. Riesz’s theorem 64

3.3. Bounded and vanishing mean oscillation 69

3.4. Kolmogorov’s theorem 73

3.5. Weighted spaces 76

3.6. The Cauchy transform and duality 77

3.7. Best constants 79

3.8. The Hilbert transform 81

Chapter 4. Topologies on the space of Cauchy transforms 83

4.1. The norm topology 83

4.2. The weak- topology 91

4.3. The weak topology 94

v

vi CONTENTS

4.4. Schauder bases 95

Chapter 5. Which functions are Cauchy integrals? 99

5.1. General remarks 99

5.2. A theorem of Havin 99

5.3. A theorem of Tumarkin 100

5.4. Aleksandrov’s characterization 102

5.5. Other representation theorems 109

5.6. Some geometric conditions 110

Chapter 6. Multipliers and divisors 115

6.1. Multipliers and Toeplitz operators 115

6.2. Some necessary conditions 118

6.3. A theorem of Goluzina 120

6.4. Some sufficient conditions 122

6.5. The F-property 127

6.6. Multipliers and inner functions 129

Chapter 7. The distribution function for Cauchy transforms 163

7.1. The Hilbert transform of a measure 163

7.2. Boole’s theorem and its generalizations 164

7.3. A refinement of Boole’s theorem 169

7.4. Measures on the circle 170

7.5. A theorem of Stein and Weiss 176

Chapter 8. The backward shift on H2 179

8.1. Beurling’s theorem 179

8.2. A theorem of Douglas, Shapiro, and Shields 180

8.3. Spectral properties 184

8.4. Kernel functions 185

8.5. A density theorem 186

8.6. A theorem of Ahern and Clark 192

8.7. A basis for backward shift invariant subspaces 192

8.8. The compression of the shift 194

8.9. Rank-one unitary perturbations 196

Chapter 9. Clark measures 201

9.1. Some basic facts about Clark measures 201

9.2. Angular derivatives and point masses 208

9.3. Aleksandrov’s disintegration theorem 211

9.4. Extensions of the disintegration theorem 212

9.5. Clark’s theorem on perturbations 218

9.6. Some remarks on pure point spectra 221

9.7. Poltoratski’s distribution theorem 222

Chapter 10. The normalized Cauchy transform 227

10.1. Basic definition 227

10.2. Mapping properties of the normalized Cauchy transform 227

10.3. Function properties of the normalized Cauchy transform 230

10.4. A few remarks about the Borel transform 241

CONTENTS vii

10.5. A closer look at the F-property 243

Chapter 11. Other operators on the Cauchy transforms 249

11.1. Some classical operators 249

11.2. The forward shift 250

11.3. The backward shift 252

11.4. Toeplitz operators 252

11.5. Composition operators 253

11.6. The Ces`aro operator 253

List of Symbols 255

Bibliography 257

Index 267


text:
# Station Guide

At this station we explore vectors and their many representations. Thinking about and comparing different approaches is encouraged throughout the resources, which range from addition of vectors to work on mechanics including projectiles, friction and forces.

Hit the spot encourages students to become comfortable with switching between different representations of vectors and helps them to appreciate why vector addition is commutative. Vector squares and Lots of vector lines! ask students to think about how geometric properties of lines are encoded in vector equations as well as thinking about the similarities and differences between Cartesian and vector form. Three lines takes the vector equation of a line into three dimensions.

Vectors play an important role when thinking about mechanics problems and this is reflected through resources such as Make it equal, which looks at particles in equilibrium, and Make it stop! where students combine vectors with ideas about kinematics and Newton’s laws of motion. Kinematics, projectiles and constant acceleration are brought together in Where did it land? and One windy day, while A frictional story explores a particle on a slope and aims to highlight that the model of friction is $F_r ≤ \mu R$ and not $F_r = \mu R$.


text:
# Recent questions tagged q150

Questions from:

### The marks secured by $400$ students in a Mathematics test were normally distributed with mean $65$. If $120$ students got more marks above $85$, the number of students securing marks between $45$ nd $65$ is

To see more, click for the full list of questions or popular tags.


text:
Elementary Geometry for College Students (6th Edition)

1) First, prove that $\triangle BAE\cong\triangle BCD$ according to SAS 2) Then, by CPCTC, $\overline{BE}\cong\overline{BD}$
*PLANNING: 1) First, prove that $\triangle BAE\cong\triangle BCD$ according to SAS 2) Then, by CPCTC, $\overline{BE}\cong\overline{BD}$ All the sides of a regular pentagon are equal and all the angles of a regular pentagon are equal. 1) $ABCDE$ is a regular pentagon. (Given) 2) $\overline{BA}\cong\overline{BC}$ and $\overline{AE}\cong\overline{CD}$ (in a regular pentagon, all the sides are equal; therefore, corresponding sides are congruent) 3) $\angle BAE\cong\angle BCD$ (in a regular pentagon, all the angles are equal; therefore, corresponding angles are congruent) So now we have 2 sides and the included angle of $\triangle BAE$ are congruent with 2 corresponding sides and the included angle of $\triangle BCD$ 4) $\triangle BAE\cong\triangle BCD$ (SAS) 5) $\overline{BE}\cong\overline{BD}$ (CPCTC)


text:
# Hurwitz's theorem (number theory)

$\left |\xi-\frac{m}{n}\right |<\frac{1}{\sqrt{5}\, n^2}.$
The hypothesis that ξ is irrational cannot be omitted. Moreover the constant $\scriptstyle \sqrt{5}$ is the best possible; if we replace $\scriptstyle \sqrt{5}$ by any number $\scriptstyle A > \sqrt{5}$ and we let $\scriptstyle \xi=(1+\sqrt{5})/2$ (the golden ratio) then there exist only finitely many relatively prime integers m, n such that the formula above holds.