text:
### Curve Fitting part 4: Validating Bayesian Code

In my previous post, I wrote a tool to use Bayesian inference to ask whether a collection of photons represented a pulsed signal, and if so, what its parameters were. It gave plausible answers, but knowing my own fallibility, I really want some more careful test before trusting its output.

I previously talked about how to implement such a correctness test in a frequentist setting. But in a Bayesian setting, what one gets are probability distributions describing our knowledge about the hypotheses - how can a program test those?

After racking my brains for a while trying to find a way to do this, I asked about it on the scipy-user mailing list, and received a few useful suggestions, the most valuable of which was to send a polite email to Professor Tom Loredo. I did, and he replied immediately with a very helpful email, and some links to other people's work on the subject.

It turns out that, in the context of Bayesian fitting, the issue is called "calibration". The key realization is that if you select a model according to your prior distribution, generate a data set, and then do your fitting to generate posterior distributions, then your "true" parameters that you used to generate the data set look just as if they had been drawn from the posterior distribution.

This makes a certain kind of sense: after all, your posterior distribution is supposed to describe the distribution of models that might have generated your data set.

So how do you turn this into a test? After all, if you just get one sample from a distribution, it's pretty hard to say anything very definite, especially when the tails - the most unlikely extreme parameters - are not necessarily very well modeled. If you try to generate another sample, you pick a different model and must then generate a different data set, so you get a new point but a totally different posterior distribution. So now you have two points, drawn from two different distributions, and your situation has not necessarily improved.

There's a trick to let you work with a large sample: you transform them to all have the same distribution. You can do this because you know the posterior distribution you're working with; in my case I have its values sampled evenly. So I can construct the cumulative distribution function and use its inverse to get the posterior probability of a value less than the true model. This should be distributed uniformly no matter the shape of the posterior.

In fact, I'd rather use a slightly different trick: instead of looking at the probability of a value less than the true model, I'll use the probability of a value more extreme than the true model. Essentially I'll combine both tails. This has a more direct bearing on the question of confidence intervals, and still results in a uniform distribution as I repeat the process many times.

Once I have a long list of many values that should be distributed uniformly, there are any number of tests I can use; I'll use the handy but not particularly good Kolmogorov-Smirnov test. My unit testing code now looks like this:

def test_credible_interval():    M = 100    N = 50    ps = []    for i in range(M):        f, p = np.random.rand(2)        events = bayespf.generate(f, p, N)        phases, fractions, r, P = bayespf.infer(events)        frac_pdf = np.average(r,axis=0)        fi = np.searchsorted(fractions, f)        p = np.sum(frac_pdf[:fi])/np.sum(frac_pdf)        p = 2*min(p, 1-p)        ps.append(p)    assert scipy.stats.kstest(ps,lambda x: x) > 0.01

Note that I don't bother testing the posterior for pulse phase. This is just laziness.

In a real Bayesian problem, there would usually be many more parameters, and I would probably not be able to evaluate the posterior on a grid like this. I'd probably be using some sort of Monte Carlo method, which would return a list of samples drawn from the posterior instead. But there are reasonable approaches in this setting too.

So far so good. But what about the probability that the signal is pulsed? In some sense hypothesis testing is just a special case of parameter fitting, but the discreteness of the "parameter" poses a problem: there's no way we can hope for a nice uniform distribution when only two values are possible. Professor Loredo very kindly sent me an unpublished note in which he addresses this problem, showing that if your code accepts a hypothesis whose posterior probability is P_crit, then a correct piece of code will be right - have chosen the correct hypothesis - with probability at least P_crit. Unfortunately P_crit is only a lower limit on the probability of getting things right; but there isn't really a way around this: suppose my code were working with a million photons a run. Then it would, in almost every case, give a probability very close to zero or one. There would be very, very few errors, no matter what value P_crit you set.

The fact that P_crit is only a lower limit does mean that this doesn't allow you to catch code that is too conservative: if your code makes fewer errors than its probabilities claim it should, this test has no way to tell that that's what's happening.

One must also choose P_crit carefully. In my example, if I choose P_crit=0.5, then code that simply chose randomly, or returned the same value all the time, would pass: after all, my priors specify equal probabilities for each model, and with P_crit=0.5 the code only needs to be right half the time. On the other hand, with P_crit really high, the code will almost never be wrong, although it only takes a few errors to fail, but it will almost never actually come to a conclusion, so you'll wait forever for evidence. There should be some fairly well-defined optimum value of P_crit, and I need to think more about what it is.

In any case, having selected P_crit and the other parameters, I can write a unit test for the hypothesis testing component:

def test_pulsed_probability():    np.random.seed(0)    p_accept = 0.75    M = 50    N = 30    accepted = 0    correct = 0    total = 0    while accepted<M:        if np.random.rand()>0.5:            f, p = np.random.rand(2)            pulsed = True        else:            f, p = 0., 0.            pulsed = False        events = bayespf.generate(f, p, N)        phases, fractions, r, P = bayespf.infer(events, n_phase=100, n_frac=101)        if P>=p_accept:            accepted += 1            if pulsed:                correct += 1        if P<1-p_accept:            accepted += 1            if not pulsed:                correct += 1        total += 1    assert 0.01<scipy.stats.binom(M,p_accept).cdf(correct)

As a final note, I'd like to thank Professor Loredo for his help, but note that any errors in the above code or description are entirely mine.

roban said...

Just saw this on arxiv (0911.2150) and thought you might be interested given you work (which I read about in your posts to the scipy list).

http://arxiv.org/abs/0911.2150

Anne M. Archibald said...

That is an interesting article. I avoid the problems they're talking about by sticking to a two-dimensional problem and using ultra-simple numerical integration, but that's only possible because I use such a simple toy problem. But their procedure looks almost perfect - you could plug it right in to a pymc model, possibly even simply using the results of a simulation you'd already run.

jstults said...

So does your unit test fail 1% of the time?

Anne M. Archibald said...

@jstults: To be honest I haven't run it a hundred times. But I know that the hypothesis testing one will probably not fail that often - it's only testing a lower limit, and that lower limit is not very strict. The credible regions test should probably fail that often, though.

I usually use two decorators to work around this issue: one called "seed" that seeds the random number generator before running the test, and a second called double_check that reruns the test (once) if it fails.

jstults said...

Hi Anne,

You seem to be really familiar with scipy, I wonder if you could recommend a tool for fitting a regression with uncertain predictor and response? I think you could define a model and use pymc (which I've never used, only browsed the docs), but I thought maybe it's a common enough problem that there's already something coded up in one of scipy's packages? Thanks for any tips.

Anne M. Archibald said...

@jstults: If I understand you correctly, you're looking to fit a model to data where both independent and dependent variables are uncertain. If you're fitting a linear model, I think OLS in scipy will do that for you. If you want some more complicated nonlinear model, I don't know of any general algorithm short of treating the errors on the independent variables as additional parameters to fit for.

jstults said...

I thought ordinary least squares was for fixed x, but then read the wikipedia article and it claims that a normally distributed predictor leads to the same result as for a fixed one (I don't remember that from any of my math classes).

Your reply got me to look further into the docs for OLS and I found scipy.odr which I think will do what I want.

Thanks.

James Philips said...

My open source project Python Equations uses Python, Scipy and Numpy - and already has ODR coded for use. It may be of some use to you.


text:
Parlay

(Redirected from Parlay (gambling))

A parlay, accumulator (or acca), combo bet or multi is a single bet that links together two or more individual wagers and is dependent on all of those wagers winning together. The benefit of the parlay is that there are much higher pay-offs than placing each individual bet separately since the likelihood of hitting all of them at once is much less. If any of the bets in the parlay lose, the entire parlay loses. If any of the plays in the parlay ties, or "pushes", the parlay reverts to a lower number of teams with the odds reducing accordingly.

Although a variety of bets can be used to build a parlay bet, correlated parlays are usually not allowed at betting sites. Correlated parlays are two or more bets from the same game that rely on a closely related outcome. Sportsbooks restrict this action because closely related bets can lead to bigger payouts in the chance of a win, which means a more substantial loss for the sportsbook.[1]

Odds and payout

Parlay bets are paid out at odds higher than the typical single game bet, but still below the "true" odds. For instance, a common 2-team NFL parlay based entirely on the spread generally has a payout of 2.6:1.[citation needed] In reality, however, if one assumes that each single game bet is 50/50, the true payout should instead be 3:1 (10% expected value for the house). A house may average 20-30% profit on spread parlays compared to perhaps 4.5% profit on individual sports mix parlay bets.

Aside from "spread" parlays, another way to parlay is to bet on two or more teams simply winning straight up. In order to calculate the payout of this parlay, one must multiply out the payout for all games. For example, if 3 teams are -385 favorites, a successful parlay on all 3 teams winning would pay out at a ratio of approximately 1/1. This is because (385/485)^3 is approximately 50%.

Examples

Typical payouts for up to 10 team parlay bet

The following is an example of a traditional Las Vegas Parlay Card, which shows the typical payouts for an up to 10 team parlay bet based on −110 prices (amount won is assuming \$100 is bet)[citation needed]:

Number Odds Amount won Payout
2 Team Parlay 2.6 to 1 \$260 \$360
3 Team Parlay 6 to 1 \$600 \$700
4 Team Parlay 11 to 1 \$1,100 \$1,200
5 Team Parlay 22 to 1 \$2,200 \$2,300
6 Team Parlay 45 to 1 \$4,500 \$4,600
7 Team Parlay 90 to 1 \$9,000 \$9,100
8 Team Parlay 180 to 1 \$18,000 \$18,100
9 Team Parlay 360 to 1 \$36,000 \$36,100
10 Team Parlay 720 to 1 \$72,000 \$72,100

Profitability of parlays in sports betting

Many gamblers have mixed feelings as to whether or not parlays are a wise play. The best way to analyze if they are profitable in the long term is by calculating the expected value. The formula for expected value is: ${\displaystyle E[X]=x_{1}p_{1}+x_{2}p_{2}+x_{3}p_{3}\dots x_{k}p_{k}}$. Since the probability of all possible events will add up to 1 this can also be looked at as the weighted average of the event. The table below represents odds.[citation needed]

Column 1 = number of individual bets in the parlay

Column 2 = correct odds of winning with 50% chance of winning each individual bet

Column 3 = odds payout of parlay at the sportsbook

Column 4 = correct odds of winning parlay with 55% chance of winning each individual bet

Number of individual bets Correct odds at 50% Odds payout at sportsbook Correct odds of winning parlay at 55%
2 3 to 1 2.6 to 1 2.3 to 1
3 7 to 1 6 to 1 5.0 to 1
4 15 to 1 12 to 1 9.9 to 1
5 31 to 1 24 to 1 18.9 to 1
6 63 to 1 48 to 1 35.1 to 1
7 127 to 1 92 to 1 64.7 to 1
8 255 to 1 176 to 1 118.4 to 1
9 511 to 1 337 to 1 216.1 to 1
10 1,023 to 1 645 to 1 393.8 to 1
11 2,047 to 1 1,233 to 1 716.8 to 1

The table illustrates that if a 55% chance of winning each individual bet were achievable, parlays would be profitable in the long term. Compare the expected value received on an individual bet at a typical price of −110 with a 55% chance of winning: ((100/110+1)*.55)−1 = .05 (exactly 5 cents won for every dollar bet on average), multiplied by 11 = .55, to the expected return on the 11 game parlay ((1234/717.8)−1) = .719 (72 cents won for every dollar bet on average). In this case a parlay has a much higher expected value than individual bets with greatly increased variance in outcomes.

format: plain


text:
# 1+n+7=13

## Simple and best practice solution for 1+n+7=13 equation. Check how easy it is, and learn it for the future. Our solution is simple, and easy to understand, so dont hesitate to use it as a solution of your homework.

If it's not what You are looking for type in the equation solver your own equation and let us solve it.

## Solution for 1+n+7=13 equation:

1+n+7=13
We move all terms to the left:
1+n+7-(13)=0
We add all the numbers together, and all the variables
n-5=0
We move all terms containing n to the left, all other terms to the right
n=5

`

## Related pages

3x 5y 199cxprime factorization of 157derivative of x cosx3x 6y 2100000 in roman numerals89-100solution to system of equations calculatorderiviative calculator0.5625 to fractiongraph 2x 3y 12percent proportions calculatorlg 2xhow to graph x 2 2x5x 2y 7180-152cos402x sinx225-144greatest common factor finderfinding greatest common factor calculatorsquare root of 6xderivative of ln1www njatc utk eduprime factorization of 1122graph 4x y 2derivative of ln 6xderivative of tan 2 x70-350is239derivative of e x2lcm of 144ln solver300-226derivative ln 3x7.5-200gcf of 84235isderiving lnderivitive of sinxwhat is 10000 in roman numeralsv lwh solve for hf x lnxantiderivative of cos 2xsina sinbroads advancedacademics com2log244&xy 2xythe lcm of 3 and 4solving binomial equations calculatorprime factorization for 80lcm of 144prime factors of 240lcm of 3 and 7square root of 1089sx equation298.9simplify x 2 4xcosh 2xlcm calculatorwhat is the prime factorization of 85the square root of 129691-32graph x 3y 9what does gcfgcf of 40 and 647 7 7 7x7-7adding fractions on a calculatormultiples of 324x 8yderive ln 2xwba aplusanywhereprime factorization for 140gcf of 75quadratic equations solver107.5 and 97.5what is 0.5625 as a fractionfactor by gcf


text:
# Help in understanding result from publication on operator theory

in my research on dilations of contractions on Hilbert spaces and manifolds I have come across this nice publication concerning the classic Sz-Nagy theorem on the Arxiv by Levy and Shalit which states the classical Sz-Nagy theorem on the existence of unitary and isometric dilations for contractions and their minimality:

http://arxiv.org/pdf/1012.4514.pdf

Right below quoting the famous theorem they mentioned that if the operator is not a unitary contraction then we must have that the larger Hilbert space K is infinite dimensional. Please forgive my ignorance but I cannot seem to understand why and it seems like a nice result I wish to understand. If the contraction to be dilated is not a unitary operator then why is the larger space embedding H is necessarily infinite dimensional? I am sorry if it was trivial and I missed it but I think I need to understand this. I thank all helpers

There are probably many ways to see this, but here is a quick one. Suppose $T$ is a contractive matrix which dilates to a unitary matrix $U$, we wish to show that $T$ is already unitary. Now, to say that the matrix $U$ dilates $T$ means there is an isometric matrix $V$ so that $$T^n = V^* U^n V$$ for all $n\geq 0$. From this it follows that the minimal polynomial $p$ for $U$ must annihilate $T$, but since all the roots of $p$ are unimodular, it follows that all the eigenvalues of $T$ are unimodular, and thus $T$ is unitary.

• Thank you Mike this is certainly a fresh approach for operator theory – kroner Mar 24 '16 at 14:41

A unitary dilation $U\in B(K)$ of $T\in B(H)$ is said to be minimal if $$\overline{span}\{U^nH : n\in \mathbb Z\} = K.$$ It is a well known result that the minimal unitary dilation is unique up to unitary equivalence.

For any contraction $T\in B(H)$, Schaeffer found a constructive version of Sz.-Nagy's dilation theorem. Specifically, $$U = \left[\begin{array}{cccccc} \ddots \\ \ddots & 0\\ & 1& 0 \\ && D_{T^*} & T \\ && -T^* & D_T & 0 \\ &&&&1 & 0 \\ &&&&&\ddots&\ddots \end{array}\right]$$ is a unitary dilation of $T$, where $D_X = (1-X^*X)^{1/2}$.

Hence, let $K' = \overline{span}\{U^nH : n\in \mathbb Z\} \subset K$. $K'$ is a reducing subspace of $U$ and $U|_{K'}$ is the minimal unitary dilation of $T$. If $T$ is not a unitary already then either it isn't an isometry ($D_T \neq 0$), a co-isometry ($D_{T^*} \neq 0$) or both. Either way it is direct to see that $K'$ is infinite dimensional from the form of the Schaeffer dilation. Therefore, by minimality, any unitary dilation of $T$ must be on an infinite dimensional Hilbert space.


text:
# Unbounded problem for certan values of factor

Hello everyone!

I want to implement the following minimization problem :

Where

C is a NxL DFT Matrix.

Gamma and Theta are constants.

Epsilon is a positive weighting factor between 0…1 and should provide a certain level of sparsity of b.

I choosed to rewrite the problem in CVX using epsilon as weighting factor for both problems:

cvx_begin
variable b(4) complex;
variable delta;
minimize(delta*(1-epsilon) + epsilon*(norm(b,1)));
subject to
(abs(imag(H_sy.'*(C*b))) - (real(H_sy.'*(C*b))-y)*tano) - delta <=0;
cvx_end

Where H_sy is just a Matrix, containing the h_k vectors with length N. In my example, L is choosen to 4.

Now, for some values of epsilon (in my case 0…0.3 ) CVX does not find a solution and reports the following:

Calling SDPT3 4.0: 14 variables, 1 equality constraints
------------------------------------------------------------

num. of constraints =  1
dim. of socp   var  = 14,   num. of socp blk  =  5
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version  predcorr  gam  expon  scale_data
NT      1      0.000   1        0
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
0|0.000|0.000|0.0e+00|3.2e+00|2.8e+01| 2.792711e+00  0.000000e+00| 0:0:00| chol *   *
1|1.000|0.964|4.2e-17|2.1e-01|2.9e+00| 1.606495e+00  0.000000e+00| 0:0:00| chol *   *
2|1.000|0.192|1.0e-15|1.7e-01|9.0e-01|-3.724179e+00  0.000000e+00| 0:0:00| chol  1  1
3|1.000|0.018|1.2e-14|1.7e-01|2.0e+01|-9.298855e+03  0.000000e+00| 0:0:00| chol  1  1
4|1.000|0.002|2.2e-13|1.7e-01|4.6e+05|-2.331268e+09  0.000000e+00| 0:0:00| chol  1  1
stop: primal infeas has deteriorated too much, 4.0e+00
5|1.000|0.000|2.2e-13|1.7e-01|4.6e+05|-2.331268e+09  0.000000e+00| 0:0:00|
prim_inf,dual_inf,relgap = 2.17e-13, 1.67e-01, 1.99e-04
sqlp stop: dual problem is suspected of being infeasible
-------------------------------------------------------------------
number of iterations   =  5
residual of dual infeasibility
certificate X          = 9.32e-23
reldist to infeas.    <= 4.91e-24
Total CPU time (secs)  = 0.10
CPU time per iteration = 0.02
termination code       =  2
DIMACS: 2.2e-13  0.0e+00  2.0e-01  0.0e+00  -1.0e+00  2.0e-04
-------------------------------------------------------------------

------------------------------------------------------------
Status: Unbounded
Optimal value (cvx_optval): -Inf

So i have the following questions:

-I assume that my minimization problem is convex? … That holds true for every value of epsilon because epsilon is just a linear factor, right?
-Does the feasibility of the problem depend on the choice of epsilon?
-Or is there any other problem of my implementation?

Im a absolute beginner in CVX and convex problems - I apologize in case the answer is very obvious.

Best & thank you in advance!

Jul

You haven’t provided the input data, so not a reproducible problem. For a given fixed (input) value of epilon, this is a convex optimization problem; although I defer judgment on whether it is a good formulation.

However my guess is that delta can go to -\infty along with
(real(H_sy.'*(C*b))-y)*tano) going to \infty, while satisfying the constraint, in such a way that delta*(1-epsilon) goes down faster than epsilon*(norm(b,1)) offsets it, hence making the problem (objective) unbounded. If that is the case, you need to rethink the model, the input data, or both.

The following input data is used:

C = 1/sqrt(4)*exp(-1i*2*pi*(0:(4-1)).'*(0:(4-1))/4);

H = 1/sqrt(4)*(randn(4,2)+1i*randn(4,2));

s = [exp(j*(pi/4 + pi/4*2*randi([0 4-1], 1, 2)))];

H_sy = exp(1i*(angle(s(1,1))-angle(s(1,:)))).*H(:,:,1);

y = 0.7*ones(2,1)/sin(pi/4);

tano = tan(pi/4);

epsilon = 0.3;

Must i really review the model?

Maybe i have another problem in my implementation: not for every manipulating of epsilon a suitable value of norm(b,1) appears:

it should be as the following:

epsilon increasing -> norm(b,1) decreasing ; epsilon decreasing -> norm(b,1) increasing.

Or is this assumption wrong? (because maybe the delta plays in there?)

You have not provided complete input data.

Sorry,

the unbounded problem occurs for epsilons between 0…0.39 .
epsilon is a value between 0…1 .

epsilon is not the only input data to your problem.

ok, then i am a bit confused
i thought you meant variables… which kind of input data is missing?

Sorry, I misread a previous post. You did provide complete input data, other than that another user might not get the same random numbers as you, which cold have some effect. Indeed, the smallest value of epsilon for which a finite optimal solution exists does depend on the random numbers.
delta can go to −∞ along with
(real(H_sy.'*(C*b))-y)*tano) going to ∞, while satisfying the constraint, in such a way that delta*(1-epsilon) goes down faster than epsilon*(norm(b,1)) offsets it, hence making the problem (objective) unbounded.


text:
### Existence and Approximations for Order-Preserving Nonexpansive Semigroups over $$\mathrm{CAT}(\kappa )$$ Spaces

Parin Chaipunya
Published: 4 May 2021
Advances in Metric Fixed Point Theory and Applications pp 111-132; doi:10.1007/978-981-33-6647-3_6


text:
News: Support us via Flattr FLATTR Link

## The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!

 Pages: [1] 2 3 ... 5   Go Down
 Author Topic: Alternate Co-ordinate systems  (Read 14514 times) Description: Alternates to the regular triplex system 0 Members and 1 Guest are viewing this topic.
Timeroot
Fractal Fertilizer

Posts: 362

The pwnge.

 « on: January 13, 2010, 03:36:44 AM »

As far as I can tell, the main three coordinate system used in 3D are:
-Triplex (Spherical) Numbers
-Cartesian Coordinates
-Quaternions. Work like Cartesian, but can be manipulate like complex numbers. One dimension is kept at 0.

I've been thinking about other possible systems. Of course, there are ones on Wikipedia, such as:
-Cylindrical coordinates, which involve a height, radius, and angle.
-Parabolic coordinates. Specified by an angle, and coefficients for two parabolas with their foci fixed at their origin.
-Parabolic cylindrical coordinates. Like parabolic coordinates, but instead of using an angle, once specifies a height.
-A whole host of other systems defines by the intersections of the second order curves, planes, and/or tori. See wikipedia for them all.

I've thought of a couple other possibilities:

-One defines a sphere with two poles, not opposite one another, and then one measures the "latitude" from each [plus a radius]. Perhaps this would be interesting as one brings the two poles closer to one another; this may go the limit of the spherical coordinates. Note this would require an extra boolean value to define which half of the sphere it lies on.

-One defines a sphere with two poles, not opposite one another, and then one measures the "longitude" from each [plus a radius]. Perhaps this would be interesting as one brings the two poles closer to one another; this may also go the limit of the spherical coordinates. This is a multivalued function when converting to cartesian coordinates if the point lies on the great circle defined by the two points, but this can be resolved (with an extra boolean) if the point from which the distance measured for the third coordinate is slightly off the center of the sphere.

-Similar to the two above, but one pole uses latitude, the other longitude. Probably all this conflicting symmetry would not apply well to fractals.

-Distance from any three predefined noncollinear points. These three points could be at (1,0,0), (0,1,0), and (0,0,1) in Cartesian coordinates, or (1,0,0), (0,1,0), and (-1,0,0), or even (0,0,0), (1,0,0), and (0,1,0). Or they could form the vertices of an equilateral triangle in the XY plane around the origin.

-It's angles from the origin, that is, the theta and phi in triplex numbers, combined with the angle from some other point; for instance, the angle from the x-axis to the point from the perspective of (1,0,0).

I don't know how well these would lend themselves to aesthetics (or even simple algebraic operations), and I'm sure twinbee has tried several of these, but perhaps some can be well defined, and may produce some interesting results. Thoughts?
 Logged

Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
Paolo Bonzini
Guest
 « Reply #1 on: January 13, 2010, 11:32:45 AM »

I suggest that you start by defining the Mandelbrot set in any of these coordinate systems; for example, in quaternions you have it as $v=vi\bar v+c$ (c has only i and j components since it's 2D).  This could give ideas about generalizing it to 3D.
 Logged
hobold
Fractal Bachius

Posts: 573

 « Reply #2 on: January 13, 2010, 05:06:00 PM »

I'm new here, but don't be alarmed. Just dropping by to point you to a kind of spherical coordinates that apparently have not yet been used to try and define some kind of triplex algebra. While it isn't possible to properly cover a sphere with coordinates that have no poles, it is possible to cover it with coordinates that have only a single pole. Here is a sketch to illustrate the general idea:

http://www.vectorizer.org/sphereFan.mpg

The red and green lines are "parallel" grid lines of "latitude" and "longitude" (the yellow great circles are just "diagonals" and an "equator"). I think this is just a reinvention of the Riemann Sphere, or some equivalent. I arrived there starting from bipolar coordinates

http://en.wikipedia.org/wiki/Bipolar_coordinates

and moved the two poles closer and closer together until they met. It wasn't until a few hours later that I realized the relation to the Riemann Sphere mapping.

http://en.wikipedia.org/wiki/Riemann_sphere

The resulting coordinate system has a few unusual properties:

- only a single pole
- "latitude" and "longitude" are symmetrical and exchangeable

and a few usual ones

- "latitude" and "longitude" grid lines intersect at a 90 degree angle
- lengths and areas are not preserved

All in all, these seem to be unusually symmetrical coordinates. I don't know if this is particularly good or bad with respect to fractals. I currently do not have any closed formulas for mapping to cartesian coordinates, but geometrically, there should exist a well-defined correspondence.

I see two outstanding choices for the (0,0) coordinate point: either the pole, or the point directly opposed to it. In either case, the two great circles (one for "latitude" and "longitude" each) could be parameterized with arc length (for purposes of adding "angles"), as has been done in the animated example illustration. I think this would make it possible to embed a 2D Mandelbrot set in a potential 3D fractal.

However, I believe a different parameterization (that spaced the smaller circles close and closer together near the pole) could be better at preserving angles, i.e. it would make the grid cells close to the pole more closely resemble squares. But then the pole would turn into some sort of singularity, with the grid cells becoming infinitesimally small as you approach the pole.
 Logged
Timeroot
Fractal Fertilizer

Posts: 362

The pwnge.

 « Reply #3 on: January 14, 2010, 01:10:42 AM »

Huh, hobold, that's a very cool coordinate system. It seems it can be interpreted a couple different ways, such as (a) a Riemann sphere projection of the bipolar coordinates, or (b) the way it actually functions in 3D, where each angle specifies the angle a plane takes with the surface of the sphere at the pole, with the restriction that the plane contains one of two perpendicular lines tangent to the pole. In order to make it slightly more square, and this probably isn't the best idea by far, one could take the cube of the angle in the 2D infinite plane (in a way...I don't know how to describe it) which would separate out the lines close to the pole a bit more.

Paolo, good point. Maybe this weekend.
 Logged

Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
hobold
Fractal Bachius

Posts: 573

 « Reply #4 on: January 14, 2010, 09:02:37 AM »

The "monopolar" coordinates are indeed made from two fans of circles originating in the pole. Here is the PoV-Ray scene file used to create the illustration, maybe someone wants to play with it:

#global_settings {
assumed_gamma 1.0
}

camera {
location  <0, 0, -4.5>
direction <0, 0, 2>
up        <0, 1, 0>
right     <1, 0, 0>
sky       <0,1,0>
look_at   <0, 0, 0>
}

union {

// the base sphere
sphere {<0, 0, 0>, 1.0
texture{
pigment { color rgb <0.1, 0.1, 0.9> }
finish{
ambient 0.1
diffuse 0.9
specular 0.3
roughness 0.001
}
}
}

#declare parts = 40;  // number of grid lines
#declare Count = 1;

#declare px = 0;
#declare py = 0;
#declare diam = 0;
#declare px2 = 0;
#declare py2 = 0;
#declare nod = 0;

#while (Count < parts)
#declare px = sin(2*pi * Count/parts);  // travel along arc
#declare py = cos(2*pi * Count/parts);

#declare Count = Count + 1;

#declare px2 = px*px;
#declare py2 = (py - 1)*(py - 1);
#declare diam = sqrt(px2 + py2);   // distance from pole
#declare nod = atan2(py - 1, px);  // angle to pole tangent plane

torus {0.5*diam, 0.005  // a "thick circle" ...
translate 0.5*diam*x  // ... touching the pole ...
rotate nod*180/pi*z   // ... and the current point
translate 1*y

texture{
pigment { color rgb <0.1, 0.9, 0.1> }
finish{
ambient 0.1
diffuse 0.9
specular 0.3
roughness 0.001
}
}
}
#end

#declare Count = 1;
#while (Count < parts)
#declare px = sin(2*pi * Count/parts);
#declare py = cos(2*pi * Count/parts);

#declare Count = Count + 1;

#declare px2 = px*px;
#declare py2 = (py - 1)*(py - 1);
#declare diam = sqrt(px2 + py2);
#declare nod = atan2(py - 1, px);

torus {0.5*diam, 0.005
translate 0.5*diam*x
rotate nod*180/pi*z
translate y
rotate 90*y   // orthogonal to the first fan of circles

texture{
pigment { color rgb <0.9, 0.1, 0.1> }
finish{
ambient 0.1
diffuse 0.9
specular 0.3
roughness 0.001
}
}
}
#end

union {
torus {1.0, 0.005}  // an "equator"
torus {1.0, 0.005   // a "diagonal"
rotate 90*z
rotate 45*y
}
torus {1.0, 0.005   // another "diagonal"
rotate 90*z
rotate -45*y
}

texture{
pigment { color rgb <0.8, 0.8, 0.2> }
finish{
ambient 0.1
diffuse 0.9
specular 0.3
roughness 0.001
}
}
}

rotate -60*x
rotate 30*z
rotate -20*x

rotate clock*360*y

}

light_source { 1*<18, 30, 20> color rgb 0.7*<1.0, 1.0, 1.0>}
light_source { <-2, -1, -20> color rgb 0.8*<1, 1, 1>}

background { color rgb <0.5,0.6,0.8> }
 Logged
hobold
Fractal Bachius

Posts: 573

 « Reply #5 on: January 14, 2010, 03:00:21 PM »

For comparison, here is a Riemann Sphere with a checkerboard mapped to it:

http://vectorizer.org/riemann.png    (seen from slightly above the pole)

The tiles get vanishingly small towards the pole, but the grid lines are indeed
circles fanned from the pole.

I think I can safely assume that I re-invented the Riemann 3D-wheel. :-)
 Logged
hobold
Fractal Bachius

Posts: 573

 « Reply #6 on: January 15, 2010, 06:07:05 PM »

I keep tinkering with the "monopolar" coordinates, and I think I should be able to provide formulas. The math is a bit awkward, and will probably be slow and imprecise in the computer, but so far it has been tractable.

With the pole at (0, 1, 0), and the spherical coordinate origin located at the pole, you can get two arc lengths for a point (Px, Py, Pz) on the unit sphere like this:

if (Py == 1) {  // check for pole
Ax = 0;
Az = 0;
} else {
Rx = Px/(Py - 1);                    // Riemann projection
Ax = atan2(2*Rx, Rx*Rx - 1);   // arc length
Rz = Pz/(Py - 1);
Az = atan2(2*Rz, Rz*Rz - 1);
}

As you can see, the numerics will become unstable near the pole (Py = 1), and you need slow trigonometric functions.

Furthermore, the perfect rotational symmetry of the Riemann sphere might cause the resulting 3D-Fractal to be a boring shape with rotational symmetry. Still, we don't know until we tested, so I won't give up yet. :-)

BTW, the monopolar coordinates could potentially be extended from a spherical surface to cover a three dimensional space. The three coordinates would be the two arc lengths above, and a signed(!) distance from the pole. Like having a negative sphere touching the original Riemann sphere at the shared pole. Not sure if those particular 3D coordinates would be good for any fractal purposes.
 « Last Edit: January 15, 2010, 06:13:59 PM by hobold » Logged
msltoe
Iterator

Posts: 187

 « Reply #7 on: January 16, 2010, 02:47:11 AM »

hobold - your idea is worth a shot.

The symmetry looks a little like one might expect for the 3-d Mandelbrot. The pole could be analogous to the positive x-axis cusp region of the 2-D M-set.

Can you figure out the inverse equation from Ax, Az to Px,Py,Pz? I started on it, but it looks a bit involved. Maybe it simplifies at the end?

-mike
 Logged
Paolo Bonzini
Guest
 « Reply #8 on: January 16, 2010, 10:35:11 AM »

if (Py == 1) {  // check for pole
Ax = 0;
Az = 0;
} else {
Rx = Px/(Py - 1);                    // Riemann projection
Ax = atan2(2*Rx, Rx*Rx - 1);   // arc length
Rz = Pz/(Py - 1);
Az = atan2(2*Rz, Rz*Rz - 1);
}

So for any length that would be:

if (Px == 0 && Pz == 0) {
Ax = 0;
Az = 0;
} else {
Length = sqrt(Px*Px+Py*Py+Pz*Pz);
Rx = Px/(Py - Length);
Ax = atan2(2*Rx, Rx*Rx - 1);   // arc length
Rz = Pz/(Py - Length);
Az = atan2(2*Rz, Rz*Rz - 1);   // arc length
}
 Logged
Paolo Bonzini
Guest
 « Reply #9 on: January 16, 2010, 11:14:50 AM »

Can you figure out the inverse equation from Ax, Az to Px,Py,Pz? I started on it, but it looks a bit involved. Maybe it simplifies at the end?

Yes (almost). First of all, of course the solution is (0,1,0) is Ax=Az=0, else you have

Rz^2 - 2 / tan Az * Rz - 1 = 0
Rz^2 - 2 * cot Az * Rz - 1 = 0

which gives

Rz = cot Az +- sqrt (cot^2 Az + 1) = cot Az +- csc Az
Rx = cot Ax +- csc Ax

I still haven't figured out how to pick the right solution but only one will give the right Ax/Az when fed back into atan2.  anyway, once you have these you can replace

Px=Rx*(Py-1)
Pz=Rz*(Py-1)

into Px^2+Py^2+Pz^2 = 1 giving

Py^2 (Rx^2+Rz^2+1) - 2 Py (Rx^2 + Rz^2) + (Rx^2 + Rz^2-1) = 0

which has only one valid solution (the other is Py=1 which is invalid):

Px = -2*Rx/(Rx^2+Rz^2+1)
Py = (Rx^2+Rz^2-1)/(Rx^2+Rz^2+1)
Pz = -2*Rz/(Rx^2+Rz^2+1)
 « Last Edit: January 16, 2010, 11:42:07 AM by Paolo Bonzini » Logged
hobold
Fractal Bachius

Posts: 573

 « Reply #10 on: January 16, 2010, 12:08:53 PM »

Can you figure out the inverse equation from Ax, Az to Px,Py,Pz? I started on it, but it looks a bit involved. Maybe it simplifies at the end?
That's the next thing I am going to try. I think I already know how I want to construct a solution geometrically:

1. An arc length indirectly specifies a plane, namely the plane of the circle of all points who have that same coordinate value.

2. The two planes of both arc length coordinates intersect in a line (except if both arc lengths are zero, but that case is easy)

3. the line intersects the unit sphere in two points, one of which is the pole

4. the line can be expressed as a ray: <starting point> + <free parameter> * <direction>
I hope to be able to express the line with the pole as starting point, then the first intersection is at parameter value zero and can be divided out, leaving us with just the one desired solution and no need to compute square roots.

I'll try to do this with the necessary mathematical rigour in the next few days.
 Logged
hobold
Fractal Bachius

Posts: 573

 « Reply #11 on: January 16, 2010, 12:13:16 PM »

So for any length that would be:

if (Px == 0 && Pz == 0) {
Ax = 0;
Az = 0;
} else {
Length = sqrt(Px*Px+Py*Py+Pz*Pz);
Rx = Px/(Py - Length);
Ax = atan2(2*Rx, Rx*Rx - 1);   // arc length
Rz = Pz/(Py - Length);
Az = atan2(2*Rz, Rz*Rz - 1);   // arc length
}

I am not sure I understand the (Py - Length) term ... ?

My own (Py - 1) comes from "subtract the Pole (0, 1, 0) from the point (Px, Py, Pz)", because I need a direction vector from the pole to the point P (for the Riemann projection). It just so happens that the Y axis is the only coordinate where that requires actual computation.
 Logged
Paolo Bonzini
Guest
 « Reply #12 on: January 16, 2010, 02:33:26 PM »

So for any length that would be:

Length = sqrt(Px*Px+Py*Py+Pz*Pz);
Rx = Px/(Py - Length);
Ax = atan2(2*Rx, Rx*Rx - 1);   // arc length

I am not sure I understand the (Py - Length) term ... ?
I'm just computing the angles Ax and Az for (Px/Length, Py/Length, Pz/Length) which gives Rx = Px/Length / (Py/Length - 1) = Px / (Py - Length).  Alternatively...

My own (Py - 1) comes from "subtract the Pole (0, 1, 0)
... when you map a point whose distance from the origin is Length, the pole is at (0, Length, 0).
 Logged
hobold
Fractal Bachius

Posts: 573

 « Reply #13 on: January 16, 2010, 04:38:23 PM »

... when you map a point whose distance from the origin is Length, the pole is at (0, Length, 0).
Ah, that one fits my mental image. Thank you! I had caged myself into the unit sphere, but the radius doesn't really matter at all.
 Logged
msltoe
Iterator

Posts: 187

 « Reply #14 on: January 16, 2010, 06:39:38 PM »

Here's the first attempt to render this fractal, doubling angles and squaring magnitude. I might've made a mistake, so others should try themselves. I used the cot+csc root only. Its possible the roots may need to be selected depending on some criteria. max iterations = 25.
 monopolar1.png (102.7 KB, 339x401 - viewed 2201 times.) « Last Edit: January 16, 2010, 06:41:21 PM by msltoe » Logged
 Pages: [1] 2 3 ... 5   Go Down


text:
What is the square root of 25/36?

Mar 4, 2018

See a solution process below:

Explanation:

We can write this expression as:

$\sqrt{\frac{25}{36}}$

We can then rewrite it as;

$\frac{\sqrt{25}}{\sqrt{36}} \implies \frac{5}{6}$


text:
So last time we were working on finding a good way to say “the darts I throw went more or less HERE”.

Points Distance $(x_i-\bar{x})^2$ $(y_i-\bar{y})^2$
(-2.2,4.1) 4.6 7.8 13.7
(-1.1,2.1) 2.4 2.9 2.9
(-0.5,0.7) 1.1 1.2 0.1
(-2.5,-3.1) 4.7 9.6 12.3
(-0.3,-3.5) 4 0.8 15.2
(2.2,3.8) 3.8 2.6 11.6
(2.4,1.8) 2.3 3.2 2
(3.8,-0.4) 3.3 10.2 0.6
(3.2,-1.8) 3.4 6.8 4.8
Avg=(0.6,0.4) Max=4.7 Avg=5 Avg=7
$\sqrt{Avg}=2.2$ $\sqrt{Avg}=2.6$

$(\sigma_x,\sigma_y)=\sqrt{\frac{1}{n}\sum_{i=1}^n((x_i-\bar{x})^2,(y_i-\bar{y})^2)}$

And in the end we came up with a formula for “standard deviation”:$\sigma=\sqrt{\frac{1}{n}\sum(x_i-\bar{x})}$
It looks like the box is at least moderately representative of where the darts went, but not many of the darts actually landed in the box. Why not? We came up with an oddball average distance away from center in the x- and y-directions, and based our rectangle on that, so why does it contain so few of the points? The picture above only contains two of the nine darts, so how can we justify calling it an ‘average’ center of any sort?

Consider for a moment what this would look like if all of the darts had a zero y-value (orange) or a zero x-value (green):

Looking at the orange dots, it looks like there are a bunch to the left and a bunch to the right and not many in the middle, so if our box is in the middle it’s probably OK if it only has a few darts in it. For the greens, five of the nine are in the box so I can’t complain too much about that. So where is the problem? The box we have drawn contains only darts that fit into BOTH categories!

Revisiting basic probability for a moment, recall how we would calculate the probability of rolling a ‘3’ on a normal die while also flipping a coin and getting ‘heads’: the probability of rolling a ‘3’ is $\frac{1}{6}$ and the probability of flipping for ‘heads’ is $\frac{1}{2}$ so the probability of both at the same time is $\frac{1}{6} \times \frac{1}{2} = \frac{1}{12}$. We have to multiply the fractions to find the probability of two independent events happening at the same time.

If we assume that our left-right error has nothing to do with the up-down error in our dart-throwing skills, then we can treat those two axes as independent and do a little multiplication to find out what is likely to be in the box. Just to see what happens, let’s redo the experiment with 100 points and keep an eye on how many points appear in the box when reduced to each axis, and also how many un-moved points stay in the box. We’ll call this our probability of being ‘in the box’. I’ll spare you the listing of 100 points, and finding the averages and standard deviations: we did that in the previous article about darts.

Wow. That graph is a bit of a mess. Even making the blue and red points semi-transparent didn’t help much. If you could count the individual dots, you would find that there are 72 blue dots in the box, 68 red dots in the box, and 50 orange ones. Coincidentally, $\frac{72}{100} \times \frac{68}{100} = 0.4896 \approx \frac{50}{100}$, which is about what we would expect since measured probability is not guaranteed to be exactly the same as a prediction.

Arguably, a dart at the far corner of the box is not as ‘good’ a shot as one in the middle of an edge, if you consider the distance from center. Perhaps something useful would be to consider a circle, but if we put a circle inside a rectangle, we lose more darts (we’re already down to about half, not very good if we want to refer to ‘most’ of them) and also circles don’t fit very well inside rectangles. It seems to me that the obvious solution is then to use an ellipse and put it outside, killing both birds with one equation. The math is going to get a little rough here, since finding out whether or not a point is inside an ellipse is a little harder than for a rectangle, and finding the equation of the right ellipse is a little tougher as well. Let’s start with a simple example and work our way up to the darts.

In this graph, there is a rectangle extending 3 units left and right from center, and 2 units up and down. The ellipse fits into the same space, and clearly is smaller than the rectangle. How are we going to figure out how big the ellipse ought to be in order to be outside the rectangle instead of inside? Let’s see if there is a value $k$ by which we can scale both the width $w$ and height $h$ of our ellipse in order to include the point $(w,h)$.

\begin{align*} y&=\frac{h}{w}\sqrt{w^2-x^2} \\ y&=\frac{h\cdot k}{w\cdot k}\sqrt{(w\cdot k)^2-x^2} \\ y&=\frac{h\cdot k}{w\cdot k}\sqrt{(w\cdot k)^2-x^2} \\ y&=\frac{h}{w}\sqrt{w^2\cdot k^2-x^2} \\ \end{align*}

Now that we have an equation with the proper scaling factor in it, let’s replace $(x,y)$ with the specific point $(h,w)$ which, coincidentally, has the same values as the height and width (measured from center, not all the way across) of our ellipse.
\begin{align*} y&=\frac{h}{w}\sqrt{w^2\cdot k^2-x^2} \\ h&=\frac{h}{w}\sqrt{w^2\cdot k^2-w^2} \\ h&=\frac{h}{w}\sqrt{w^2(k^2-1)} \\ h&=\frac{h}{w}\cdot w\cdot \sqrt{k^2-1} \\ h&=h\cdot \sqrt{k^2-1} \\ 1&=\sqrt{k^2-1} \\ 1&=k^2-1 \\ 2&=k^2 \\ \sqrt{2}&=k \\ \end{align*}

Well, perhaps that wasn’t too bad. Starting with the equation of an ellipse of width $w$ and height $h$, substitute $w$ in for $x$ and set the result to $h$, and also make sure to use $hk$ and $wk$ for the height and width of the ellipse we want to find. After than, cancel common factors, square everything to get rid of the square root, and solve for $k^2$. Finally, take the square root to get our answer in terms of $k$. Whoever would have guessed that all we have to do is multiply $w$ and $h$ by a simple constant? Then the final equation, which circumscribes the rectangle extending $w$ units left and right and $h$ units up and down, looks like this:

\begin{align*} y&=\frac{h'}{w'}\sqrt{w'^2-x^2} \\ y&=\frac{h\sqrt{2}}{w\sqrt{2}}\sqrt{((w\sqrt{2})^2-x^2} \\ y&=\frac{h}{w}\sqrt{2w^2-x^2} \\ \end{align*}

And the resulting graph looks like this:

Beautiful! Now how many of the points is this ellipse going to contain?

There are 32 orange dots outside the blue ellipse, so there are 68 inside. I just eyeballed that from the graph, so if that’s off by one don’t be too surprised. $100-32 = 68$, so 68% of the darts are within the ellipse. That’s in line with the 72 blue and 68 red dots above! So perhaps we are at the point where we can say, “Most of my darts are inside that ellipse!”

But…

What happens if our high darts tend to be to the right, and low ones to the left?

That is a story for next time. Until then, keep throwing those darts!

(Visited 70 times, 1 visits today)


text:
## CryptoDB

### Paper: MV3: A new word based stream cipher using rapid mixing and revolving buffers

Authors: Nathan Keller Stephen D. Miller Ilya Mironov Ramarathnam Venkatesan URL: http://eprint.iacr.org/2006/341 Search ePrint Search Google MV3 is a new word based stream cipher for encrypting long streams of data. A direct adaptation of a byte based cipher such as RC4 into a 32- or 64-bit word version will obviously need vast amounts of memory. This scaling issue necessitates a look for new components and principles, as well as mathematical analysis to justify their use. Our approach, like RC4's, is based on rapidly mixing random walks on directed graphs (that is, walks which reach a random state quickly, from any starting point). We begin with some well understood walks, and then introduce nonlinearity in their steps in order to improve security and show long term statistical correlations are negligible. To minimize the short term correlations, as well as to deter attacks using equations involving successive outputs, we provide a method for sequencing the outputs derived from the walk using three revolving buffers. The cipher is fast --- it runs at a speed of less than 5 cycles per byte on a Pentium IV processor. A word based cipher needs to output more bits per step, which exposes more correlations for attacks. Moreover we seek simplicity of construction and transparent analysis. To meet these requirements, we use a larger state and claim security corresponding to only a fraction of it. Our design is for an adequately secure word-based cipher; our very preliminary estimate puts the security close to exhaustive search for keys of size < 256 bits.
##### BibTeX
@misc{eprint-2006-21832,
title={MV3: A new word based stream cipher using rapid mixing and revolving buffers},
booktitle={IACR Eprint archive},
keywords={cryptographic protocols / stream cipher, random walks, expander graph, cryptanalysis},
url={http://eprint.iacr.org/2006/341},
note={This is the full version of a paper to appear in CT-RSA 2007 (about 9 pages longer, with appendices) miller@math.rutgers.edu 13431 received 9 Oct 2006},
author={Nathan Keller and Stephen D. Miller and Ilya Mironov and Ramarathnam Venkatesan},
year=2006
}


text:
# Make an ed clone

ed is the standard text editor on Unix systems. Your goal is to write an ed clone.

Write a program that reads an input stream and for every received end of line character, print ? followed by a end of line character.

• The communication has to interactive. Means the program needs to output as soon as possible and has to accept more input after that.
• There are no input lines that are longer than 105 characters + end of line character
• You can choose which character or sequence you use as end of line character, as long as it does not contain any alphanumerical characters nor the ? character.
• The program should not output anything else.

Shortest code wins.

## Example Python Script

#/usr/bin/env python3

import sys

for line in sys.stdin:
print("?")

• How is this an ed clone? It doesn't seem to edit files. Jan 7 at 22:12
• @WheatWizard It is a joke. Because ed returns ? for almost every input. Jan 10 at 11:41

# Charcoal, 5 bytes

?ＷＳＤ⎚

Try it online! Link is to verbose version of code. Explanation:

?

Write a ? to the canvas, but don't print anything yet.

ＷＳ

Repeatedly input lines until there is nothing left to input...

Ｄ

... dump the canvas with a trailing newline.

⎚

Clear the canvas so that nothing gets output at the end.

• I upvoted that for respect. I like your answer. Jan 8 at 1:01

$_="?" Try it online! # Ruby + -pl, 5 bytes $_=??

Try it online!

# Nibbles, 2 bytes

@"?"

That's 4 nibbles at half a byte each in the binary form.

@ is the first line of input but auto maps all lines if there's more input after the first line.

Despite the simplicity of this problem I must thank it for making me make sure Nibbles is properly lazy enough to do interactive IO right. There was an issue in that it adds a newline at termination unless your last character was a newline (to not double print newlines), but that wasn't being done lazy enough and so it wasn't interactive enough to satisfy this question. But I've fixed it in latest commit (you'll need latest unstable version of nibbles).

# Python 3, 40 27 bytes

for i in open(0):print("?")

Try it online!

-13 thanks to @ovs

• You can use open(0) instead of sys.stdin and get rid of the input
– ovs
Jan 7 at 21:39


text:
# The Chern-Simons/Wess-Zumino-Witten correspondence

I have often seen a relationship being alluded to between these two theories but I am unable to find any literature which proves/derives/explains this relationship.

I guess in the condensed matter physics literature this is the "same" thing which is referred to when they say that one has propagating chiral bosons on the boundary of the manifold if there is a Chern-Simons theory defined in the interior("bulk")

Let me quote (with some explanatory modifications) from two papers two most important aspects of the relationship that is alluded to,

1. "...It is well known that any Chern-Simons theory admits a boundary which carries a chiral WZW model; however these degrees of freedom are not topological (the partition function of Chern-Simons theory coupled to such boundary degrees of freedom depends on the conformal class of the metric on the boundary)..."

2. "...In general if the pure Chern-Simons theory (of group $G$) at level k is formulated on a Riemann furface then the number of zero-energy states equals the number of conformal blocks of the WZW model of $G$ at level $k' = k - \frac{h}{2}$ ($h=$the quadratic Casimir of G in the adjoint representation)..(and when the Riemann surface is a torus) the number of conformal blocks is equal to the number of representations of $\hat{G}$ at level $k'$.."

• I would like to know of a reference(s) (hopefully pedagogical/introductory!) which explains/proves/derives the above two claims. (..I looked through various sections of the book by Toshitake Kohno on CFT which deals with similar stuff but I couldn't identity these there..may be someone could just point me to the section in that book which may be explains the above claims but may be in some different garb which I can't recognize!..)
-
As far as I remember Witten's famous paper "Jones polynomial & ... " also discusses this, in the section when tries to calculate examples - at some point he needs Verlinde formula for WZ to calculate explicily something. The idea (AFAIR) is simple take locally M=R\times Sigma, main point is to choose appropriate gauge fixing, as far as I remember A_0 = 0 , then in this gauge dA_0 is Lagrange multiplier in Feynman integral which sits on the space of the flat connections... If I will remember details I will write them... –  Alexander Chervov Jul 2 '12 at 19:20

Quantum field theories are understood/formalized at various levels of detail (e.g. action functional only, space of states/partition function only, full functorial QFT, full extended QFT). Accordingly there are such different levels at which people will say "It is well-known that...".

For the general holographic principle there are still lots of gaps, but for the special case of 3dChern-Simons-TQFT/2dWZW-CFT things are pretty well understood.

The nLab entry

holographic principle -- Ordinary Chern-Simons theory / WZW-model

gives a list of pointers, some of which coincide with what is being said in other replies here.

First of all there is a direct relation between the action functionals: the CS action functional on a manifold with boundary is not gauge invariant. The boundary term that appears is the action functional of the WZW model (the topological term, at least, and the kinetic term with due fine-tuning).

More abstractly, the Chern-Simons action for $G$ simply connected arises by transgression of a differential universal characteristic map on higher smooth moduli stacks $\mathbf{B}G_{conn} \to \mathbf{B}^3 U(1)_{conn}$. The WZW action (the topolological term) similarly arises simply by the (differentially twisted) looping (as smooth $\infty$-stacks) of this map.

Then the famous original observation: geometric quantization of this action functional yields a space of states for Chern-Simons theory that may be naturally identified with the partition function of the WZW model.

To promote this further to a relation between ful QFTs, one needs to know what the full QFT corresponding to Chern-Simons theory is. This hasn't as yet been fully established via quantization, but the expectation is that it is what the Reshetikhin-Turaev construction gives when fed the modular tensor category of loop group representations of the gauge group. Assuming this, there is a very detailed construction by Fuchs-Runkel-Schweigert and others that effectively construct the rational WZW CFT (as a full Segal-style CFT) from the TQFT.

Recently the holographic aspect of this construction has been further amplified by Kapustin-Saulina and then by Fuchs-Schweigert-Valentino.

See at the above link for references to all these items.

-
@Urs Schreiber Thanks for the details. Can you elaborate on this point you made that "The boundary term that appears is the action functional of the WZW model (the topological term, at least, and the kinetic term with due fine-tuning)" AFAIK because the Chern-Simons action is not gauge invariant a gauge transformation on it produces an "extra" term which looks like one of the terms of the WZW action. But I can't see how this can be interpreted to say that there is an effective WZW theory on the boundary when there is CS theory in the bulk. –  Anirbit Jul 3 '12 at 15:06
@Urs Schreiber Can you also link to the Kapustin-Saulina paper that you mentioned? (..infact the first of my italicized quotes is an adaptation from a Kapustin-Saulina paper..) –  Anirbit Jul 3 '12 at 15:08
Hi Nairbit, my comment above is really just an extended pointer to what I have written at that nLab entry, which contains the links that you are looking for and more: ncatlab.org/nlab/show/holographic+principle#OrdinaryCSWZWModel . –  Urs Schreiber Jul 6 '12 at 12:20
Sorry, my fingers introduced a key twist. I meant to type Anirbit. Sorry. (Wasn't there once the possibility to edit comments here? Where did it disappear to?) –  Urs Schreiber Jul 6 '12 at 12:21
@Urs Schreiber Thanks for the details. But don't see anywhere in your links a derivation of the fact that about the bulk partition function of Chern-Simons' theory generically having a dependence on the conformal class of the metric on the boundary (..and how specific boundary conditions for the gauge field can remove that dependence..) This to my mind is one of the most important aspects of the correspondence. Can you give some references/explanations towards that? –  Anirbit Jul 11 '12 at 15:14

The boundary of a Chern-Simons theory carries a Wess-Zumino-Witten model...

This comes from the following relation between the parameters of the two theories. Recall that a Chern-Simons theory is determined by an element $$\xi \in \hat H^4(BG,\mathbb{Z}),$$ an element in the degree four differential cohomology of the classifying space of the gauge group. Often $\xi$ can be identified with an element in ordinary cohomology, and in turn with just an integer, called level. Recall that a Wess-Zumino-Witten-model is determined by an element $$\eta \in \hat H^3(G,\mathbb{Z}).$$ Now, there is a transgression map $$t: \hat H^4(BG,\mathbb{Z}) \to \hat H^3(G,\mathbb{Z})$$ which converts a Chern-Simons theory into a WZW model.

This is discussed (using bundle gerbes) in

The states of the CS theory form the conformal blocks of the WZW model...

This is a result of Witten, a crucial ingredient for the relation between Chern-Simons theory and the Jones polynomial. You might want to start in Section 5 of

• E. Witten: Quantum Field Theory and the Jones Polynomial, Commun. Math. Phys. 121,351-399 (1989)

Another source with general information about the Chern-Simons states is Section 5 of

They key information is formula (5.15) in the latter paper. It expresses the partition function of the WZW model (coupled to a gauge field, and with field insertions) by scalar products of CS states. The next formula (5.16) has (5.15) reduced to the torus, relating it to representations of $G$.

-
The main derivation though of what you wrote is from the reference I posted. –  Chris Gerig Jul 2 '12 at 21:34
@Konrad Waldorf Thanks for the answer. Seems Alexander Chervov also recommended section 5 of this paper of Witten's. About Gawedski's lectures - probably its a bad question to ask! - how far back do I have to start to understand equation 5.15? (...earlier my experience has been that Gawedski's writings can be very terse!..I am just wondering whether I have to read that entire lecture to understand this point!..) –  Anirbit Jul 3 '12 at 15:18
@Anirbit: the paper of Gawedzki's is a review about certain standard aspects of conformal field theory. If you want to understand the formula, I'm afraid you will either have to read the whole paper, or to go to other sources that help you to understand at least Section 5. Gawedzki's writing might be terse, but it's also a landmark of elaborate, substantiated, and correct writing! –  Konrad Waldorf Jul 3 '12 at 23:28
@Konrad Waldorf I guess I will first look through the section 5 of Witten's paper and then will venture into Gawedski's writings. (..experience has been that Witten's writings are much more beginner friendly!..) –  Anirbit Jul 4 '12 at 20:11

The immediate paper that comes to mind is Topological Gauge Theories and Group Cohomology by Dijkgraaf and Witten, starting on pg403. The Wess-Zumino term appears because the Chern-Simons functional is not gauge invariant, and the variation of this action depends on the connection at the boundary surface. This paper references Witten's Non-abelian Bosonization in Two Dimensions in talking about the WZW model and CFT, so I think this would be useful to check out.

As for the second comment, pg411-413 brings up the conformal block stuff, but I'm not sure it explains what you want. It does have references:
1) Extended Chiral algebras and modular invariant partition functions (Karpilovsky, et.al.)
2) Spectra of WZW models with arbitrary simple groups (Felder, et.al.)
3) Taming the conformal zoo (Moore, Seiberg)
Hopefully one of those leads you to what you desire.

-

You are unlikely to find a proof of these claims, because Chern-Simons theory, as a quantum field theory in 3 dimensions, has not been precisely formulated mathematically.

You can find some partial results in the book Bakalov, Kirillov, Lectures on tensor categories and modular functor.

-
More precisely, what has not been carried out precisely is the quantization of the Chern-Simons Lagrangian to a full TQFT. On the other hand, it is expected that once done, the result is the TQFT defined by the modular tensor category given by, say, the loop group representations of the given loop group. Under this assumption, the correspondence CS-TQFT / WZW-CFT has been made precise by Fuchs-Runkel-Schweigert et al. see ncatlab.org/nlab/show/FFRS-formalism . –  Urs Schreiber Jul 3 '12 at 7:53

There is yet one more perspective on the relation between $G$-Chern-Simons theory and the WZW-model on $G$: the background B-field of the latter can be regarded as being the prequantum circle 2-bundle in codimension 2 for a "higher/extended geometric quantization" of Chern-Simons theory.

This is spelled out a bit at

In brief the story is this:

We have constructed in Cech cocycles for differential characteristic classes a refinement of the generator of $H^4(B G, \mathbb{Z})$ to a morphism of smooth moduli $\infty$-stacks $\mathbf{c}_c : \mathbf{B}G_c \to \mathbf{B}^3 U(1)_c$ from that of $G$-principal bundles with connection to that of circle 3-bundles (bundle 2-gerbes) with connection

(for $G$ a simple, simply connected Lie group).

This is such that when transgressed to the mapping $\infty$-stack from a closed compact oriented 3d manifold $\Sigma_3$ it yields the Chern-Simons action functional

$$\exp(2 \pi i \int_{\Sigma_3} [\Sigma_3, \mathbf{c}_{conn}]) : CSFields(\Sigma_3) = [\Sigma_3, \mathbf{B}G_{conn}] \to U(1) \,.$$

But one can similarly transgress to mapping stacks out of a $0 \leq k \leq 3$-dimensional manifold $\Sigma_k$. For $k = 1$ with $\Sigma_1 = S^1$ one obtains a canonical circle 2-bundle (circle bundle gerbe) with connection on the smooth moduli stack of $G$-principal connections on the circle

$$\exp(2 \pi i \int_{S^1} [S^1, \mathbf{c}_{conn}]) : [\Sigma_1, \mathbf{B}G_{conn}] \to \mathbf{B}^2 U(1) \,.$$

Now since $\mathbf{B}$ is "categorical delooping" while $[S^1, -]$ is "geometric looping", the mapping stack on the left if not quite equivalent to $G$ itself, but it receives a canonical map from it

$$\bar \nabla_{can} : G \to [S^1, \mathbf{B}G_{conn}] \,.$$

In fact, the internal hom adjunct of this map is a canonical $G$-principal connection $\nabla_{can}$ on $S^1 \times G$, and this is precisely that from def. 3.3 of the article by Carey et al that Konrad mentions in his reply.

So the composite

$G \to [S^1, \mathbf{B}G_{conn}] \stackrel{transgression}{\to} \mathbf{B}^2 U(1)_{conn}$

is thw WZW circle 2-bundle on $G$, or equivalently the Chern-Simons prequantum circle 2-bundle in codimension 2.

(The math parser here gets confused when I type in the full formulas. But you can find them at the above link).

-

I learned this correspondence from Bos and Nair's paper "Coherent State Quantization of Chern-Simons Theory" and that is what I recommend. I wrote a short review of the part that you are interested in: check the second section of my paper (http://arxiv.org/abs/1311.1853) on Yang-Mills-Chern-Simons theory. Constant k comes from the wave-functional and quadratic casimir in the adjoint representation comes from the gauge invariant integral measure. Some knowledge on geometric quantization is required. You can find that in V.P.Nair's "Quantum Field Theory" book (or B.C.Hall's "Quantum theory for mathematicians" book in more detail). Also in Nair's book you can check the WZW section(17.6). It explains where quadratic casimir comes from in the "Dirac determinant in two dimensions"(17.7) calculation.

-