text:
## Kodai Mathematical Journal

### The effect of Fenchel-Nielsen coordinates under elementary moves

#### Abstract

We describe the effect of Fenchel-Nielsen coordinates under elementary move for hyperbolic surfaces with geodesic boundaries, punctures and cone points, which generalize Okai's result for surfaces with geodesic boundaries. The proof relies on the parametrization of the Teichmüller space of surface of type (1,1) or (0,4) as a sub-locus of an algebraic equation in $\mathbf{R}^3$. As an application, we show that the hyperbolic length functions of closed curves are asymptotically piecewise linear functions with respect to the Fenchel Nielsen coordinates in the Teichmüller spaces of surfaces with cone points.

#### Article information

Source
Kodai Math. J., Volume 41, Number 2 (2018), 421-439.

Dates
First available in Project Euclid: 2 July 2018

https://projecteuclid.org/euclid.kmj/1530496851

Digital Object Identifier
doi:10.2996/kmj/1530496851

Mathematical Reviews number (MathSciNet)
MR3824860

Zentralblatt MATH identifier
06936462

#### Citation

Tan, Dong; Liu, Peijia; Liu, Xuewen. The effect of Fenchel-Nielsen coordinates under elementary moves. Kodai Math. J. 41 (2018), no. 2, 421--439. doi:10.2996/kmj/1530496851. https://projecteuclid.org/euclid.kmj/1530496851

format: plain


text:
## Statistics: Show that the sum of two independent Cauchy random variables is Cauchy.

Given the fact that X and Y are independent Cauchy random variables, I want to show that Z = X+Y is also a Cauchy random variable.

I am given that X and Y are independent and identically distributed (both Cauchy), with density function f(x) = 1/(∏(1+x2)) . I also use the fact the convolution integral for X and Y is ∫f(x)f(y-x)dx .

My book says to use the following hint:

f(x)f(y-x) = (f(x)+f(y-x))/(∏(4+y2)) + 2/(∏y(4+y2))(xf(x)+(y-x)f(y-x)) .

Using this hint, I'm able to solve the rest of the problem, but I can't figure out how to prove that this hint is true.

Any help would be much appreciated : )
 PhysOrg.com science news on PhysOrg.com >> Leading 3-D printer firms to merge in $403M deal (Update)>> LA to give every student an iPad;$30M order>> CIA faulted for choosing Amazon over IBM on cloud contract

 Similar discussions for: Statistics: Show that the sum of two independent Cauchy random variables is Cauchy. Thread Forum Replies Calculus & Beyond Homework 1 Calculus & Beyond Homework 6 Calculus & Beyond Homework 1 Calculus & Beyond Homework 13 Introductory Physics Homework 0


text:
## Design a data model to store N datasets along with the values of N parameters sets and the results of runs using the parameter values on the datasets

Let’s say we have N different input static datasets D_n, for example (don’t focus on the example but more on the concept here) using N=3;
a dataset D_1 composed of images,
a dataset D_2 of features
and a dataset D_3 of objects.

On each dataset, I can apply some parameters P_n to do some (simple or sometime quite complex) computations on it.

Let’s call a ‘run’, the results of the combination of the application of
some defined set of values for the image parameters P_1 applied to the images dataset D_1 (which would lead to some processed data D_1′ corresponding to the dataset D_1) +
some defined set values of the features parameters P_2 applied to the features dataset D_2 (which would lead to some processed data D_2′ corresponding to the dataset D_2) +
some defined set of values of the object parameters P_3 applied to the object dataset D_3 (which would lead to some processed data D_3′ corresponding to the dataset D_3) .

How would you designed a relational database (I’m using PostgreSQL but I guess it’s not important at this stage) so that we can store both 1) the results of each and every run using different sets of defined values for the parameters P_n on the datasets D_n and 2) the values or the parameters used for getting these results.

For the moment, each time I want to run the computations using different parameter values, I change these values in a config file, overwriting the previous ones, and I output results to files on the disk, which also got overwritten for each new run. But I’d like to keep them all now.
Another problem that I have is that I’m writing images and some geographical data on the disk, mainly raster files, which are quite huge, therefore it would probably not be a good idea to store them in the database but only keeping a link (to the file) in the DB.
Last but not least, if I store values for parameters in a `parameter` table in my database, I cannot run the computation in parallel on the same database as I would need different values setup in the same table for two different runs.

That’s why I’m searching to better design and organize my datasets and parameters when playing with different sets of values.

## webserver – How strict should I be in rejecting unexpected HTTP request parameters redux?

I read this: How strict should I be in rejecting unexpected query parameters?

Answer: No, do not error out on unexpected query string parameters.

But I just got a requirement from our security guy that I must do so. Not only for unexpected query string, but also unexpected cookies, headers, and unexpected everything. Reasoning:

It is possible that some component in the tech stack has a vulnerability like buffer overflow, sql injection, or other vulnerabilities of this sort. Unexpected data in requests may be a malicious attempt to find and exploit such a vulnerability. Therefore it is needed to return a 4xx response in such a situation. The blackbox should be configured to detect a spike of 4xx responses and react appropriately: ban the ip that produces such responses, notify the admin that the server is under attack, and the likes. The 4xx response is not meant for the attacker but for our security systems.

I don’t know… it seems to make sense, but it contradicts advice found in stack exchange sites.

Where is the error of such reasoning?

## mysql – mysqli_query() expects at least 2 parameters, 1 given in Inicio de sesión

soy nuevo en esto de MySQL y PHP.

Tengo un codigo que es de inicio de sesión algo viejo que usa mysql_query(), sin embargo si lo pongo como mysqli_query() me da el siguiente error:

Warning: mysqli_query() expects at least 2 parameters, 1 given in /home/path/index.php on line 26

Las lineas que dan el error son estas:

``````\$query =mysqli_query("SELECT * FROM usertbl WHERE username='".\$username."' AND password='".\$password."'");

\$numrows=mysqli_num_rows(\$query);
if(\$numrows!=0)

{
while(\$row=mysqli_fetch_assoc(\$query))
``````

Que podré hacer para corregirlo?

I’m having problems after configuring recaptcha, it generates the following warning "Recaptcha required parameters are missing!". Has anyone had this problem?

## physics – How to make a variable height jump controlled by parameters?

I’m trying to make a variable height jump controlled by parameters. I want to be able to specify the max height of my jump, and a time to max height. I also want to be able to specify a min jump height.
My understanding is we construct a jump by using max_height and time_to_max to calculate gravity.

``````func gravity(height, peak_time):
return -2 * height / pow(peak_time * 2, 2)
``````

Because min_jump_height uses the same gravity as max jump height, it’s time to peak is not determined directly, but through the other variables. I calculate my initial velocity based on my min_jump_height and gravity:

``````func initial_velocity(gravity, min_height):
return sqrt(2 * -gravity * min_height)
``````

As usual, I apply gravity each frame:

``````velocity += gravity * delta
``````

How do I make it so that each frame the jump button is held a little more is added to velocity such that the original peak height is hit at peak time? This is, in effect, compensating through interpolation for if my initial velocity had been targeted to my max_height instead of my min_height. I imagine there might be more than one valid form of interpolation to solve this problem and I’d be interested in any of them, but the simplest will do.

## How to match only part of URL and redirect URL with parameters in .htaccess?

If the query string is irrelevant then it can simply be ignored. (You can’t match the query string anyway with the `RewriteRule` directive.)

Try the following in your root .htaccess file to redirect the request:

``````RewriteEngine On
RewriteRule ^index.php/path/some-path/some-subpath\$ /category/? (L,R=301)
``````

In per-directory .htaccess files, the URL-path matched by the `RewriteRule` pattern has the directory-prefix removed. In other words, it does not start with a slash, `^index.php....` instead of `^/index.php....`.

The `?` on the end of the `RewriteRule` substitution is required in order to remove the query string (if any) from the request. Otherwise `parameter=1` will be passed through and appended to the target URL.

This will match any query string, including an empty one.

## 8 – How to set required POST parameters for routes

With GET method we can do something like this

``````example.user
path: 'example/{user}'
defaults:
_controller: 'DrupalexampleControllerExampleController::content'
requirements:
_permission: 'access content'
user: ^(a-zA-Z0-9_)+
``````

so it sets `user` param as required and also limits its format.

But I’d like to do something similar with POST method. Tried this, but not working:

``````example.user
path: 'example'
methods:  (POST)
defaults:
_controller: 'DrupalexampleControllerExampleController::content'
requirements:
_permission: 'access content'
user: ^(a-zA-Z0-9_)+
``````

EDIT:

Sure I can set some logic inside controller like this, but it doesn’t feel right:

``````public function store(Request \$request) {
\$params = json_decode(\$request->getContent(), TRUE);
//I'm trying to avoid using these conditions inside controller methods
if(empty(\$params('user'))){
//return error response
}else{
if (!preg_match('/^(a-zA-Z0-9_)+/', \$params('user'))) {
//return error response
}
}
//return success response
}
``````

So what’s drupal way to do it?

## c# – Refactoring constructor that has too many parameters

You are right, 8 parameters -all strings- makes the constructor a good candidate for a code review.

Consider some of the next points.

### Essential attributes first

Look the message model and figure out which attributes are necessary to initialize an instance in a consistent state. Reduce the number of arguments to the essential. Add setters or functions for the rest.

If all 8 attributes are required and read-only, there’s not too much to do.

### Encapsulation

Consider encapsulating correlated parameters. For example, A, B and C might be placed together into a new class. Find out which parameters change together, at the same time, due to the same reasons.

It reduces the number of arguments at the cost of one more class (complexity).

### Use creational patterns

Instead of initializing messages directly from any place in the code source, do It from factories or builders.

### Arrays

If none of the above works, try an array of parameters. Given the lack of meaningful param’s names, it’s probably the simplest solution.

Regarding arrays, I posted a question where I ask about its suitability. I was reluctant to trust in such a solution. However, the answers helped me out to be less reticent, so check it out if you also dislike this solution. It might change your mind about this.

### Inheritance

Eventually, you will realise that messages are good candidates for inheritance. Segmenting messages by attribute generates a little overhead because sooner than later you ends up asking for the type `if(message.getType() == ...)` all over the code.

## Solving coupled ODE symbolically for the parameters

I’m trying to solve the following system:

$$dot{x_1} = -i w_1 x_1+ i s_1 x_2$$
$$dot{x_2} = -i w_2 x_2- i s_2 x_1$$

For $$X(t)_{1,2}$$,
where $$x_{1,2} = X(t)_{1,2}cdot e^{ip(t)_{1,2}}$$

I know the solution is:

$$dot{X_1}=s_1X_2sin(p_1 – p_2)$$
$$dot{X_2}=s_2X_1sin(p_1 – p_2)$$

I tried the following:

``````x1 = X1(t)*E^(I*p1(t));
x2 = X2(t)*E^(I*p2(t));

x1dot = -I*w1*x1 + I*s1*x2;
x2dot = -I*w2*x2 + I*s2*x1;

x1d = D(x1, t);
x2d  = D(x2, t);

{{X1s(t), X2s(t)}} =
{X1(t), X2(t)} /.
Simplify(
Solve(
{x1d == x1dot, x2d == x2dot},
{X1(t), X2(t)}))
``````

But The result I get is:

$$-frac{i left(text{x1d} text{p2}'(t)+text{s1} e^{i text{p2}(t)} text{X2}'(t)+text{w2} text{x1d}right)}{e^{i text{p1}(t)} left(-text{w1} text{p2}'(t)+text{s1} text{s2}-text{w1} text{w2}right)},-frac{i left(text{w1} text{X2}'(t)+frac{text{s2} text{x1d}}{e^{i text{p2}(t)}}right)}{-text{w1} text{p2}'(t)+text{s1} text{s2}-text{w1} text{w2}}$$

I’m not sure if Mathematica can use Euler’s formula to simplify the complex exponents and get to the known solution. I guess it’s possible but I’m not sure how to do it


text:
# Article

Full entry | PDF   (0.3 MB)
Keywords:
oscillation; sublinear differential equation; integral averages
Summary:
New oscillation criteria are given for the second order sublinear differential equation $[a(t)\psi (x(t))x^{\prime }(t)]^{\prime }+q(t)f(x(t))=0, \quad t\ge t_0>0,$ where $a\in C^1([t_0,\infty ))$ is a nonnegative function, $\psi , f\in C({\mathbb R})$ with $\psi (x)\ne 0$, $xf(x)/\psi (x)>0$ for $x\ne 0$, $\psi$, $f$ have continuous derivative on ${\mathbb R}\setminus \lbrace 0\rbrace$ with $[f(x)/\psi (x)]^{\prime }\ge 0$ for $x\ne 0$ and $q\in C([t_0,\infty ))$ has no restriction on its sign. This oscillation criteria involve integral averages of the coefficients $q$ and $a$ and extend known oscillation criteria for the equation $x^{\prime \prime }(t)+q(t)x(t)=0$.
References:
[1] B. Ayanlar and A. Tiryaki: Oscillation theorems for nonlinear second-order differential equations. Comput. Math. Appl. 44 (2002), 529–538. DOI 10.1016/S0898-1221(02)00167-0 | MR 1912848
[2] Y. Chen: On the oscillation of nonlinear second order equations. J.  South China Normal Univ. Natur. Sci. Ed. 2 (1986), 99–103. MR 1005446
[3] S. R. Grace and B. S. Lalli: On the second order nonlinear oscillations. Bull. Inst. Math. Acad. Sinica 15 (1987), 297–309. MR 0942790
[4] S. R. Grace: Oscillation theorems for second order nonlinear differential equations with damping. Math. Nachr. 141 (1989), 117–127. DOI 10.1002/mana.19891410114 | MR 1014421 | Zbl 0673.34041
[5] S. R. Grace and B. S. Lalli: Integral averaging techniques for the oscillation of second order nonlinear differential equations. J.  Math. Anal. and Appl. 149 (1990), 277–311. DOI 10.1016/0022-247X(90)90301-U | MR 1054809
[6] S R. Grace: Oscillation theorems for nonlinear differential equations of second order. J.  Math. Anal. and Appl. 171 (1992), 220–241. DOI 10.1016/0022-247X(92)90386-R | MR 1192503 | Zbl 0767.34017
[7] M. Kirane and Y. V. Rogovchenko: Oscillation results for a second order damped differential equation with nonmonotonous nonlinearity. J.  Math. Anal. Appl. 250 (2000), 118–138. DOI 10.1006/jmaa.2000.6975 | MR 1893881
[8] T. Kura: Oscillation theorems for second order nonlinear differential equations. Proc. Amer. Math. Soc. 84 (1982), 535–538. DOI 10.1090/S0002-9939-1982-0643744-8 | MR 0643744
[9] M. K. Kwong and J. S. W. Wong: On an oscillation theorem of Belohorec. SIAM J.  Math. Anal. 14 (1983), 474–476. DOI 10.1137/0514040 | MR 0697523
[10] H. J. Li and C. C. Yeh: Oscillation of second order sublinear differential equations. Dynamic Systems Appl. 6 (1997), 529–534. MR 1487476
[11] J. V. Manojlović: Oscillation criteria for second order sublinear differential equation. Math. Comp. Modelling 30 (1999), 109–119. DOI 10.1016/S0895-7177(99)00151-X | MR 1753568
[12] J. V. Manojlović: Oscillation criteria for second order sublinear differential equation. Computers and Mathematics with Applications 39 (2000), 161–172. DOI 10.1016/S0898-1221(00)00094-8
[13] J. V. Manojlović: Integral averages and oscillation of second order nonlinear differential equations. Computers and Mathematics with Applications 41 (2001), 1521–1534. DOI 10.1016/S0898-1221(01)00117-1 | MR 1831815
[14] Ch. G. Philos: Oscillation of sublinear differential equations of second order. Nonlinear Anal. 7 (1983), 1071–1080. DOI 10.1016/0362-546X(83)90016-0 | MR 0719359 | Zbl 0525.34028
[15] Ch. G. Philos: On second order sublinear oscillation. Aequationes Math. 27 (1984), 242–254. DOI 10.1007/BF02192675 | MR 0762684 | Zbl 0545.34026
[16] Ch. G. Philos: Integral averaging techniques for the oscillation of second order sublinear ordinary differential equations. J.  Austral. Math. Soc. (Series  A) 40 (1986), 111–130. DOI 10.1017/S1446788700026549 | MR 0809730 | Zbl 0583.34028
[17] Ch. G. Philos: Oscillation theorems for linear differential equations of second order. Arch. Math. (Basel) 53 (1989), 482–492. DOI 10.1007/BF01324723 | MR 1019162 | Zbl 0661.34030
[18] Ch. G. Philos: Integral averages and oscillation of second order sublinear differential equations. Diff. Integ. Equat. 4 (1991), 205–213. MR 1079621 | Zbl 0721.34026
[19] J. Yan: A note on second order sublinear oscillation theorems. J.  Math. Anal. and Appl. 104 (1984), 103–106. DOI 10.1016/0022-247X(84)90034-9 | MR 0765043 | Zbl 0609.34045
[20] J. S. W. Wong: An oscillation criterion for second order sublinear differential equations. Conf. Proc. Canad. Math. Soc. 8 (1987), 299–302. MR 0909919 | Zbl 0624.34027
[21] J. S. W. Wong and C. C. Yeh: An oscillation criterion for second order sublinear differential equations. J.  Math. Anal. Appl. 171 (1992), 346–351. DOI 10.1016/0022-247X(92)90348-H | MR 1194084
[22] J. S. W. Wong: Oscillation criteria for second order nonlinear differential equations involving general means. J.  Math. Anal. Appl. 247 (2000), 489–505. DOI 10.1006/jmaa.2000.6855 | MR 1769091 | Zbl 0964.34028

Partner of


text:
I follow the blog “Math Jokes 4 Mathy Folks“.  A recent post gave a game/riddle you can play with kids or even post a set of questions on some social media site and play with your friends.  The post is “Can I Get Your Digits“.

So, here are the questions you can ask:

[Step-1] Pick a number with more than four digits (keep it secret).
[Step-2] Add the digits of the number together (keep it secret).
[Step-3] Subtract this sum from the original number (keep it secret).
[Step-4] From [Step-3] give me all the digits except for one of them (keep that digit secret).
[Step-5] I will ‘magically’ guess the missing (secret) digit!

The ‘magic-guess’ is: Add up the digits given to you and then add what ever number it takes to get to the nearest multiple of nine and that number is the missing digit.

So for example: the number 87694. When the digits are added you get 34.  When you subtract 36 from 87694 you get 87660.  Below is a table for each of the possible missing digits from number 87660.

Missing the ‘0’ … 8+7+6+6 = 27 (The missing digit is ZERO)
Missing the ‘6’ … 8+7+6+0 = 21 (The missing digit is SIX)
Missing the ‘7’ … 8+6+6+0 = 20 (The missing digit is SEVEN)
Missing the ‘8’ … 7+6+6+0 = 19 (The missing digit is EIGHT)

Now here is an explanation of why this always works.

The way numbers are represented is in what is called a ‘Place Value System’.  In this system a number can be thought of as a sum of the digits of the number times a power of 10 (for a base 10 number).  The power of 10 depends on the ‘Place’ of the digit.  The ‘least-significant’ digit (the on on the right end of a number) can be thought of as that digit times $10^{0}$.  The next ‘Place’ is called the 10’s place and can be thought of as that digit times $10^{1}$, with the next ‘Place’ being the 100’s place or the digit times $10^{2}$ and so forth.

So for example:

$87694\quad =\quad 8\times {10}^{4}+7\times {10}^{3}+6\times {10}^{2}+9\times {10}^{1}+4\times {10}^{0}$

And this representation is equivalent to the following one when you replace the powers of 10 with the corresponding addition problem:

$8\left( 1+9999 \right) +7\left( 1+999 \right) +6\left( 1+99 \right) +9\left( 1+9 \right) +4$

It is now clear how this ‘magic guess’ works. When you distribute each digit over the corresponding sum you get the following:

$8+8\left( 9999 \right) +7+7\left( 999 \right) +6+6\left( 99 \right) +9+9\left( 9 \right) +4$

Regrouping you get the following very suggestive formula:

$(8+7+6+9+4)\quad +\quad 8\left( 9999 \right) +7\left( 999 \right) +6\left( 99 \right) +9\left( 9 \right)$

This is clearly the sum of the digits of the original number plus another number that is clearly a multiple of nine:

$\sum { digits\_ of(87694) } \quad +\quad 9\left[ 8\left( 1111 \right) +7\left( 111 \right) +6\left( 11 \right) +9\left( 1 \right) \right]$

The main thing to realize here is that when you subtract $\sum { digits\_ of(87694) }$ from the original number you are left with a number that (whatever its actual digits are) is a multiple of nine.

Finally it is the case that any number that is a multiple of nine also has the property that the number resulting from summing its digits is also a multiple of nine. This final fact is what you use to find the missing digit. Leaving out a single digit will ‘disturb’ the sum so it is no longer a multiple of nine and you only need sum up what you are given and find that number that causes the sum to be a multiple of nine to deduce the missing digit.

Notice: When the dropped digit is either a ‘0’ or a ‘9’ your magic ‘guess’ should be: “You left out either a 9 or a 0.”

Notice: This explanation can be extended to an arbitrary number of digits and thus it would be a proof.

Notice: That a multiple of nine also has the properties that the sum of its digits is also a multiple of nine can be explained in exactly the same way as the explanation above goes. So assume some number is a multiple of nine:

$X\quad =\quad 9x$

Now write X as a sum of its digits with each one times its corresponding power of ten:

$X\quad =\quad \sum _{ i=0 }^{ n }{ { a }_{ i } } { 10 }^{ i }$

Notice that we can write each term of the sum as a digit of the the original number times the quantity $\left( 1+9\cdots 9 \right)$ where the symbol “$9\cdots 9$” is 9 or 99 or 999 or 9999 and so forth.

$X\quad =\quad { a }_{ 0 }+\sum _{ i=1 }^{ n }{ { a }_{ i } } \left( 1+9\cdots 9 \right)$

This way of writing the number makes it clear what happens when each digit is distributed over the its corresponding sum and the the sum regrouped so that the sum of the digits of the original number are distinct from the rest of the number.

$X\quad =\quad { a }_{ 0 }+\sum _{ i=1 }^{ n }{ { a }_{ i } } +\sum _{ i=1 }^{ n }{ { a }_{ i } } \left( 9\cdots 9 \right)$

Now it is clear that each term of the rightmost sum can be factored by the number nine giving the formula below. The symbol “$1\cdots 1$” is 1 or 11 or 111 or 1111 and so forth.

$X\quad =\quad { a }_{ 0 }+\sum _{ i=1 }^{ n }{ { a }_{ i } } +\quad 9\sum _{ i=1 }^{ n }{ { a }_{ i } } \left( 1\cdots 1 \right)$

Recalling that the original number is a multiple of nine we get the following:

$9x\quad =\quad { a }_{ 0 }+\sum _{ i=1 }^{ n }{ { a }_{ i } } +\quad 9\sum _{ i=1 }^{ n }{ { a }_{ i } } \left( 1\cdots 1 \right)$

Finally subtracting the rightmost sum from both sides of the formula and factoring out the number nine we get the following which does show that the sum of the digits of the original number is a multiple of nine.

$9\left[ x-\sum _{ i=1 }^{ n }{ { a }_{ i } } \left( 1\cdots 1 \right) \right] ={ a }_{ 0 }+\sum _{ i=1 }^{ n }{ { a }_{ i } } \quad$


text:
Bon - 11 months ago 208
C++ Question

# vcruntime140.dll vs vcruntime140d.dll

What are the difference between these two dlls vcruntime140.dll and vcruntime140d.dll? Why do we need them? Are they both part of the Microsoft Visual C++ 2015 Redistributable?

Have googled for quite some time, but couldn't find anything that I can understand.

Some background: I have a C# program that works on a Windows 10 machine but doesn't work on Windows Vista, and looks like it is because there is no vcruntime140d.dll on my Windows Vista machine.

• a release version which does NOT end with a d - for example: vcruntime140.dll
• a debug version which ends with a d - for example: vcruntime140d.dll


text:
# Applying Inverse Function Theorem to open set $A$ to prove $f^{-1}:f(A) \to A$ is a differentiable map

This is the first question in Spivak's Calculus on Manifolds from the chapter on the Inverse Function Theorem.

Problem 2-36. * Let $A \subset \mathbb{R}^n$ be an open set and $f : A \to \mathbb{R}^n$ a continuously differentiable $1$-$1$ function such that $\det f'(x) \neq 0$ for all $x$. Show that $f(A)$ is an open set and $f^{-1} : f(A) \to A$ is differentiable. Show also that $f(B)$ is open for any open set $B \subset A$.

To prove that $f^{-1}:f(A) \to A$ is differentiable, I began by applying the Inverse Function Theorem to some $x\in A$, which gives an inverse function from some subset of $f(A)$, lets call it $W_{f(x)}$ to a subset of $A$, called $V_x$, thus giving $f^{-1}:W_{f(x)} \to V_x$ as a differentiable map. How then is $f^{-1}:f(A) \to A$ differentiable? Do I generate inverse functions for each $y\in f(A)$ and define $f^{-1}:f(A) \to A$ as a piecewise function such that $f^{-1}:W_{f(x_1)} \to V_{x_1}$ is the function that applies when we are mapping an element that's contained in $W_{f(x_1)}$? Or, do I just need one of the differentiable maps $f^{-1}:W_{f(x)} \to V_x$ to prove this?

• If $f$ is locally invertible, that means it is locally an open map. Use that $f(\cup A_\alpha) = \cup f(A_\alpha).$ – Will M. Jun 12 '18 at 22:52
• $f^{-1} : f(A) \to A$ is differentiable at every $f(x) \in f(A)$ since we have neighbourhood $W_{f(x)}$ such that $f^{-1}|_{W_{f(x)}} : W_{f(x)} \to V_{x}$ is differentiable at every point in $W_{f(x)}$. – kelvinn aja Jun 13 '18 at 1:43
The function $f^{-1} : f(A) \to A$ is said to be differentiable if it is differentiable at each point in the domain, that is, at each $f(x) \in f(A)$. Since for each point we have a neighbourhood $W_{f(x)} \subseteq f(A)$ of $f(x)$ and a neighbourhood $V_x \subseteq A$ of $x$ such that $$f^{-1}|_{W_{f(x)}} : W_{f(x)} \to V_x$$ is differentiable, we have shown that $f^{-1} : f(A) \to A$ is differentiable.


text:
# 5x5x5 OBTM upper bound

#### xyzzy

##### Member
(Has anyone else attempted such computations before? I didn't find anything.)

tl;dr: 143 OBTM 141 OBTM 135 OBTM (2017-10-31) 134 OBTM (2018-05-15) 130 OBTM (2018-05-20).

I finished writing a 5x5x5 solver about three weeks ago, and in the time since I've mostly been working on trying to get a "good" upper bound for the 5x5x5 God's number in OBTM. I'm not entirely satisfied with this analysis, because according to this older thread with move counts of human solves, reduction can and should take much fewer moves than the upper bound I got, but anyway.

We divide the solving process into seven main phases, the last of which is a 3x3x3 solve. Some of these phases will in turn be divided into subphases that are easier to analyse. The division of phases is largely based on Charles Tsai's documentation of his 4x4x4 solver.

(Side note: the code I use for generating these tables is mostly not shared with the solver, apart from trivial utility functions like calculating binomial coefficients and such, so I'm not fully certain the numbers are correct. Independent confirmation would be awesome. Also, the solver itself usually finds a reduction in around 70 to 75 moves with about a minute of CPU time, which is… very far from the bound presented here, to say the least.)

Phase 1: Solving the UD centres to the UD faces

E: Obsolete; see post #7 by qq280833822.

Someone with more disk space to spare (and using a programming language where accessing hundred-gigabyte arrays isn't a PITA) could probably do a breadth-first search on the whole state space of C(24,8)^2 ~ 541 billion states, but that someone is unfortunately not me. This is split into two subphases, where the first subphase solves the T-centres and the second subphase solves the X-centres. As an optimisation, we can reduce the move count by one if we skip the last move of the first subphase before proceeding to the second subphase.

Obsoleted by later analysis; preserved for posterity.

Moves allowed: U, D, R, L, F, B, Uw, Dw, Rw, Lw, Fw, Bw
Code:
0     5
1     66
2     900
3     9626
4     80202
5     329202
6     302146
7     13324
Obsoleted by later analysis; preserved for posterity.

Moves allowed: U, D, R, L, F, B, Uw, Dw, Rw, Lw, Fw, Bw
Code:
0     -
1     1
2     -
3     8
4     64
5     363
6     3604
7     27752
8     159086
9     392648
10     151261
11     684

Upper bound: 7 + 11 = 18 12 moves.

Phase 2: Solving the RL centres to the RL faces; FB centres to the FB faces; and wing parity

Moves allowed: U, D, R, L, F, B, Uw, Dw, Rw2, Lw2, Fw2, Bw2
Code:
0     1
1     2
2     33
3     374
4     3848
5     40230
6     409051
7     3816922
8     27309148
9     108088828
10     153042267
11     38271627
12     291452
13     17

Upper bound: 13 moves.
Cumulative upper bound: 31 25 moves.

Phase 3: Orienting all midges and separating wings into two orbits

Note that no restriction is placed on the centres in this phase, unlike the corresponding phase in Tsai's solver. We allow either all the edges to be oriented, or all the edges to be flipped.

Obsoleted by later analysis; preserved for posterity.

Moves allowed: U, D, R, L, F, B, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2
Code:
0     1
1     2
2     33
3     382
4     3920
5     45980
6     515594
7     4882282
8     37725852
9     214944909
10     748549490
11     1177896283
12     541147752
13     43045056
14     297920
15     288

Upper bound: 15 13 moves.
Cumulative upper bound: 46 44 38 moves.

(See post #5 in this thread for how the upper bound was reduced from 15 moves to 13 moves.)

Phase 4: "Domino" reduction

Again, no restriction is placed on the centres here. This is divided into two subphases. In the first subphase, the pieces needed to form four tredges are placed in the L and R layers. (This takes no moves at all ~52% of the time, or ~78% of the time if we get to do a z rotation as well, but we're doing a worst-case analysis, not an average-case analysis.)
In phase 3, we have the wings separated into two orbits (each of 12 pieces), such that within each orbit, each wing has a different pair of colours. (To borrow terminology from earlier work, arbitrarily call one of the orbits "low" and the other "high".) The low orbit has eight wings in the L, R layers, as does the high orbit.

Let A be the set of colour pairs of the eight wings in the low orbit and the L, R layers, and B be the set of colour pairs of the eight wings in the high orbit and the L, R layers. We have |A| = |B| = 8 and |A∪B| ≤ 12 (there are only 12 possible colour pairs), so by inclusion-exclusion, |A∩B| ≥ 4, i.e. there are at least four colour pairs shared between A and B. We can choose any four such colour pairs, and then move the midges and wings with those colour pairs onto the L and R layers.

This has C(8,4) ⋅ C(8,4) ⋅ C(12,4) cases to consider, where the four low wings are already in the L, R layers, the four high wings likewise, and the four midges can be anywhere. We do not constrain the four low wings or the four high wings to stay in the L and R layers throughout the subphase; we only require that they end up there.

(The actual computation was done with a BFS through the C(12,4)^3 cases with the wings being anywhere, and then filtered to include only the cases where the low/high wings start on the L and R layers.)

We can use the same inclusion-exclusion trick on, say, the low wings and the midges (instead of low wings and high wings), but that leads to an upper bound of 7 moves, which is worse than the 6 moves we have here.

In the second subphase, four tredges are formed out of the pieces chosen in the previous subphase, and these tredges are placed in the E slice positions (FL, BL, BR, FR). The moves used here are almost the same as in phase 5, but off by a z rotation.

Moves allowed: U, D, R, L, F2, B2, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2
Code:
0     343000
1     24750
2     194785
3     977228
4     672305
5     204640
6     8792
Moves allowed: U2, D2, R, L, F2, B2, Uw2, Dw2, Fw2, Bw2
Code:
0     1
1     3
2     17
3     110
4     761
5     4944
6     30453
7     178759
8     995736
9     5144375
10     22521971
11     67281036
12     84004674
13     17258876
14     146284

Upper bound: 6 + 14 = 20 moves.
Cumulative upper bound: 66 64 58 moves.

Phase 5: 3x3x3 reduction (except centres)

In this phase, all the tredges are formed; the centres remain in a "3-colour solved" state.

Moves allowed: U, D, R2, L2, F2, B2, Rw2, Lw2, Fw2, Bw2
Code:
0     1
1     4
2     26
3     156
4     999
5     5892
6     36376
7     222480
8     1301886
9     7238228
10     36410756
11     144974952
12     343690470
13     262142742
14     16825016
15     1216

Upper bound: 15 moves.
Cumulative upper bound: 81 79 73 moves.

Phase 6: Centres

Three subphases: one for the U and D centres, one for the R and L centres, and one for the F and B centres. The depth distributions are identical for all three.

Partially obsolete.

Moves allowed (for solving R, L, F and B centres): U2, D2, R, L, F, B, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2
See post #9 for details. Upper bound is 27 moves.

Moves allowed (for solving U and D centres): U, D, R2, L2, F2, B2, Rw2, Lw2, Fw2, Bw2
Code:
0     1
1     -
2     -
3     -
4     2
5     6
6     29
7     146
8     331
9     189
10     592
11     940
12     1560
13     1064
14     40

Upper bound: 3⋅14 = 42 27 + 14 = 41 moves.
Cumulative upper bound: 123 121 115 114 moves.

Phase 7: 3x3x3

Upper bound: 20 moves.
Cumulative upper bound: 143 141 135 134 moves.

Last edited:

#### Herbert Kociemba

##### Member
Someone with more disk space to spare (and using a programming language where accessing hundred-gigabyte arrays isn't a PITA) could probably do a breadth-first search on the whole state space of C(24,8)^2 ~ 541 billion states, but that someone is unfortunately not me.
It is not so hopeless as you think. You can reduce the problem by 16 symmetries, then you have two symmetry-reduced coordinates with size each of about C(24,8)/16 = 50000. These can be combined to a coordinate of size about 50000^2*16= 40GB. You can construct a pruning table with 2 bits for each entry, so the pruning table will not have more than 10 GB. Just for a breadth first search you only need 1 bit per entry, so even 5 GB will be enough.

#### xyzzy

##### Member
It is not so hopeless as you think. You can reduce the problem by 16 symmetries, then you have two symmetry-reduced coordinates with size each of about C(24,8)/16 = 50000. These can be combined to a coordinate of size about 50000^2*16= 40GB. You can construct a pruning table with 2 bits for each entry, so the pruning table will not have more than 10 GB. Just for a breadth first search you only need 1 bit per entry, so even 5 GB will be enough.
We don't need two symmetry-reduced coordinates, but only one symmetry-reduced coordinate and one non-reduced coordinate, right? 5 GB would fit in my free RAM pretty snugly, so I'm going to give this a shot. I'm somewhat afraid that the computation will take many hours and I'll stay up all night staring at a progress bar slowly fill up, though.

#### Herbert Kociemba

##### Member
We don't need two symmetry-reduced coordinates, but only one symmetry-reduced coordinate and one non-reduced coordinate, right? 5 GB would fit in my free RAM pretty snugly, so I'm going to give this a shot
Yes this ist true and surely a simpler approach. Additionally you then need a table which transforms the non-reduced coordinates to new non-reduced coordinates by conjugation with each of the 16 symmetries.

#### xyzzy

##### Member
For phase 3, we don't actually have to look at all 2^11 C(24,12) / 2 ~ 2.8 billion states, since we're free to assign the starting midge position to be whatever we want. For instance, if we consider the midges to always start as being oriented, the distribution changes to:

Code:
 0          1
1          -
2          -
3          -
4          8
5        128
6        863
7       3990
8      23788
9     151274
10     611614
11    1110867
12     661700
13     132522
14       7364
15         37
This doesn't improve on the upper bound, but we can look at other starting midge orientations (since we don't care if the reduction leaves the cube with flipped tredges at the end).

Of the 288 antipodal positions, 37 of them have midges solved at the start, 21 have midges in the S slice flipped, 75 have midges in the E slice flipped, and 75 have midges in the M slice flipped, so 208 of the 288 antipodes have D8 symmetry on the midges along some axis. One of the antipodes is given by having all wings solved and all midges flipped, which is about as symmetric as you can get.

Anyway, if we start with the six midges at UF, UL, UB, FL, BL and DR flipped, this is the distribution.

Code:
 0         -
1         -
2         -
3         -
4         -
5         9
6       194
7      2888
8     30212
9    216169
10    857006
11   1246820
12    346302
13      4556

This reduces the upper bound for phase 3 to 13 moves, and the overall upper bound to 141 moves. This is the "best" we can do with a fixed starting midge orientation (every starting orientation has some case that needs at least 13 moves), but a potential improvement in this direction is to use set cover techniques to try different starting orientations.

Last edited:

#### qq280833822

##### Member
I've just finished the analysis of the phase1 of your algorithm. The analysis result shows that phase 1 can be solved in 12 moves. Here is the depth distribution of phase 1.
Code:
Depth      Positions             Total
0                 1                 1
1                 4                 5
2                98               103
3             2,036             2,139
4            41,096            43,235
5           824,950           868,185
6        16,300,291        17,168,476
7       311,709,304       328,877,780
8     5,376,178,126     5,705,055,906
9    67,415,029,758    73,120,085,664
10   316,925,367,079   390,045,452,743
11   150,473,278,964   540,518,731,707
12       398,860,134   540,917,591,841
BTW, It seems that the moves spend on phase 6 is 3*14, wherein the centers of UD/FB/RL are independently solved. Will the depth be significantly reduced by solving centers of 3 axes simultaneously?

The number of states in this phase is C(8, 4)^6 = 117,649,000,000. If all 48 symmetries are considered, the search space will be reduced to about 2.5 billion unique states. If we have a really fast solver, maybe it can be finished in several hours or several days at most.

Last edited:

#### xyzzy

##### Member
Nice! The phase 1 distribution matches mine up to 6 moves, which was where I stopped my computation.

BTW, It seems that the moves spend on phase 6 is 3*14, wherein the centers of UD/FB/RL are independently solved. Will the depth be significantly reduced by solving centers of 3 axes simultaneously?

The number of states in this phase is C(8, 4)^6 = 117,649,000,000. If all 48 symmetries are considered, the search space will be reduced to about 2.5 billion unique states. If we have a really fast solver, maybe it can be finished in several hours or several days at most.
Yeah, I think phase 6 is wasting a lot of moves, but I really don't know where to even begin shaving moves off that.

Within ⟨U, D, R2, L2, F2, B2, Rw2, Lw2, Fw2, Bw2⟩, the R/L/F/B faces are always in a "vertical bars" state (C(4,2)^2 = 36), and in total all the centres can be solved in 16 moves with this restriction:
Code:
0 1
1 -
2 -
3 -
4 12
5 18
6 68
7 294
8 986
9 3489
10 9953
11 15459
12 34228
13 54528
14 45832
15 11340
16 192
(I ran this computation last year, but ended up not using these results.) So we could do something like two subphases: first subphase brings the RLFB centres to a vertical bars position, then second subphase solves all centres (at most 16 moves). The first subphase has only C(8,4)^4 = 24010000 positions to consider (~1.5e6 reduced by symmetry), and we can use ⟨U2, D2, R, L, F, B, Uw2, etc.⟩ to solve this, so the "edge pairing" part has only 12!^2/2 states because EO is preserved (instead of 24!/2 if EO isn't preserved), which allows for good pruning tables to be constructed.

(I have an optimal reduction solver, but it's extremely slow, partly because of how ineffective the edge pairing pruning tables are when there are no move restrictions at all. I think we would run into the same problem if we want to do phase 6 all at once, which has no meaningful move restrictions, which in turn makes pruning less effective, which makes exhaustive searching slower.)

A lot less ambitious than doing phase 6 without subphases, but still likely to reduce the upper bound for phase 6 significantly.

#### xyzzy

##### Member
Some experimentation on optimising phase 6 (and more generally phases 4 through 6), hopefully an actual lowering of the bound within the next few days as I verify my code and run a bunch of exhaustive searches.

So we could do something like two subphases: first subphase brings the RLFB centres to a vertical bars position, then second subphase solves all centres (at most 16 moves). The first subphase has only C(8,4)^4 = 24010000 positions to consider (~1.5e6 reduced by symmetry), and we can use ⟨U2, D2, R, L, F, B, Uw2, etc.⟩ to solve this, so the "edge pairing" part has only 12!^2/2 states because EO is preserved (instead of 24!/2 if EO isn't preserved), which allows for good pruning tables to be constructed.
This might work, but it's much slower than I'd expected it to be. I have a solver for solving UDRL centres and pairing all the edges within the move set {U, D, R, L, F2, B2, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2}, and I tweaked the algorithm slightly to be able to return suboptimal solutions (basically, multiplying the pruning table values by a fixed constant greater than 1).

For solving the UD centres, preserving RL and ignoring FB, with the aforementioned set of allowed moves, this is the move count distribution:
Code:
 0:  1
1:  0
2:  0
3:  0
4:  6
5:  12
6:  19
7:  178
8:  459
9:  285
10:  722
11:  1274
12:  1440
13:  496
14:  8
The upper bound here is 14 moves, which isn't better than what we had before. The antipodal positions are this state with 3 of the x-centres wrong and this other state also with 3 of the x-centres wrong (and the mirrors of these).

The cases with either of these patterns on both the UD centres and the RL centres can be solved in 21-24 moves, and for the remaining cases we can solve the UD centres and RL centres separately in at most 13+14 = 27 moves (since we won't have the 14-move cases on both axes), so this reduces the upper bound of phase 6 by a grand total of one move to 41 moves, bringing the total upper bound down to 134 moves.

(that's a lot of work for shaving off one move, wtf)

Solving to a position with the UDRL centres in a bars state doesn't seem to be faster. ("Faster" in the sense of CPU time needed, which is the real bottleneck here.) I also ran the computation for solving UD centres without preserving RL and FB, but less than one quarter of the way through I noticed that the 14-move positions were still taking 14 moves even if RL didn't need to be preserved, so I aborted it.

The 21-move solution of the "worst case" position was produced with the suboptimal solver, because I ran the optimal solver for two hours and it got nowhere. We might need to do some extra face aligning (because this isn't a unique "worst case" position), which explains why the actual bound we get for this position is 24 moves. I think at most two alignments are needed, but it's 4 am and I can't be bothered to work out the cases now (and it's not necessary anyway).

Given that the worst case of "axis-by-axis" solving comes from the case with only x-centres unsolved, we might get a better bound by solving the x-centres then the t-centres. Or we could just throw this approach out and come up with something completely different and """""original""""", like solving the centres first then doing edge pairing.

This is the move count distribution for solving one orbit of the wings after phase 3 (ignoring all centres):
Code:
total states: 479001600
distance 0: 1 nodes
distance 1: 6 nodes
distance 2: 55 nodes
distance 3: 454 nodes
distance 4: 3287 nodes
distance 5: 21258 nodes
distance 6: 125118 nodes
distance 7: 680883 nodes
distance 8: 3278462 nodes
distance 9: 13363986 nodes
distance 10: 43383252 nodes
distance 11: 103042620 nodes
distance 12: 156868710 nodes
distance 13: 124957752 nodes
distance 14: 33212116 nodes
distance 15: 63640 nodes
Solving the other orbit of wings while preserving the first (and still ignoring all centres) takes at least 18 moves in the worst case. Assuming the worst case is indeed 18 moves, we could decrease the upper bound of phase 4 + phase 5 (currently 35 moves) to 15+18 = 31 moves. However, this would take way too much computation to do directly (~3 minutes per state per thread and there are ~3 million of them with symmetry reduction), and there's no "room" for splitting up into subphases because that would probably waste 4+ moves.

This is the distribution for solving the wings relative to each other (i.e. the edges are all paired, except the midges might be wrong), still ignoring all centres:
Code:
total states: 14999140
distance 0: 1 nodes
distance 1: 2 nodes
distance 2: 7 nodes
distance 3: 24 nodes
distance 4: 103 nodes
distance 5: 619 nodes
distance 6: 4287 nodes
distance 7: 28697 nodes
distance 8: 187493 nodes
distance 9: 1087267 nodes
distance 10: 4323558 nodes
distance 11: 7657009 nodes
distance 12: 1708625 nodes
distance 13: 1448 nodes
(note: this is with full symmetry reduction)
This looks a bit more promising, because it seems that we can solve the midges in relatively few moves and it's way faster (~275 milliseconds per state per thread). A random sample of two thousand states:
Code:
  8:  1
9:  2
10:  2
11:  10
12:  33
13:  129
14:  441
15:  563
16:  702
17:  117
This could potentially cut the upper bound for phase 4 + phase 5 to 13+17 = 30 moves, which is still pretty high, but we'll take it.

Last edited:

#### xyzzy

##### Member
>triple post

Here we optimise phases 4+5 by doing something completely different instead. This cuts the bound for those two phases to 13+18 = 31 moves, which is four moves fewer than what we had in the original analysis (20+15 = 35). Just to avoid confusion, these will be called phases A4 and A5 instead of just "phase 4" and "phase 5". (I still think it's possible to optimise the original phase 4 more—it just needs more disk space to store the computation than I have free.)

Phase A4: Pairing wings (ignoring midges) + parity of wings relative to midges

At the end of phase 3, we have the wings separated into a "low" orbit and a "high" orbit, each with twelve pieces. Thus we can define the permutations of the wings within the orbits as $$L,H\in S_{12}$$, with the permutation of the midges $$M\in S_{12}$$. In this phase, we solve $$H^{-1}L$$ (the goal is to have $$H^{-1}L=e$$, the identity permutation) and $$\operatorname{sgn}(M^{-1}L)$$.

As the parity of all 24 wings is solved in phase 2, this ensures that $$H^{-1}L$$ can only be an even permutation, so this phase has (12!/2) × 2 ~ 4.8e8 cases. An example of a case where $$H^{-1}L=e$$ and $$\operatorname{sgn}(M^{-1}L)=1$$ is given by doing the scramble Rw2 U2 Rw2 U2 Rw2.

This is to reduce the number of actual solving that is needed. It turns out that, regardless of whether parity is considered or ignored, the upper bound for this phase will be 13 moves. The distribution for this phase can be computed with a straightforward breadth-first search, which takes only a couple of minutes, whereas the distribution for the next phase has to be done with loads of optimal solves. Thus increasing the number of cases in this phase (which is relatively fast) in exchange for halving the number of cases in the next phase (which is very slow) is a net win in terms of CPU time needed. It also (possibly) reduces the upper bound.
Moves allowed: U, D, R, L, F2, B2, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2
Code:
0:         1
1:         3
2:        20
3:       149
4:      1198
5:      8608
6:     67897
7:    496029
8:   3476696
9:  21726393
10:  98243928
11: 237241650
12: 116562172
13:   1176856

Upper bound: 13 moves.

Phase A5: 3×3×3 reduction (except centres)

This is split into two subphases. The first subphase reduces to a set of roughly one million cases that can be solved in at most 10 moves, and the second subphase finishes edge pairing in at most 10 moves. The first subphase takes at most 7 moves 99.989% of the time, and for the remaining 0.011%, we run an optimal solver on all of those cases.

(Note: the computation was done with symmetry reduction, but the distributions here are for all cases.)

For this subphase, the set of destination states we choose consists of the states with $$H^{-1}L=e$$ that are solvable in at most 10 moves. The computation was done by first filtering out the states where the individual orbits are solvable in 10 moves (47879988 cases in total), then doing optimal solves for those. Note that this set does not restrict to even parity like phase A4 does; 741052 of the states have even parity and 207024 have odd parity.

Moves allowed: U, D, R, L, F2, B2, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2
Code:
  0:    741052
1:   2155220
2:   8027812
3:  15356860
4:  49350248
5:  69508264
6:  75709048
7:  18625784
≥8:  26512
Moves allowed: U, D, R, L, F2, B2, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2
Code:
  0:       1
1:       0
2:       3
3:      14
4:      77
5:     534
6:    1584
7:    7247
8:   45800
9:  197708
10:  695108
These are the 26512 states that cannot be reduced to the "10 moves from solved" set in 7 or fewer moves. An optimal solver (wrt the move set) was used. It's plausible that the 18-move states can be solved in fewer moves if we use stuff like M' U2 M, since this falls outside of the standard move set.

Moves allowed: U, D, R, L, F2, B2, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2
Code:
 15:    112
16:   3584
17:  22176
18:    640

Upper bound: max(7+10, 18) = 18 moves.

Upper bound for reduction: 12 (phase 1) + 13 (phase 2) + 13 (phase 3) + 13 (phase A4) + 18 (phase A5) + 41 (phase 6) = 110 moves.
Upper bound for the full solve: 110 + 20 = 130 moves.


text:
# Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma

Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted setting, the dependency of the complexity of the distributed Lovász Local Lemma (LLL) on the chosen LLL criterion exhibits a sharp threshold phenomenon: They proved that, under the LLL criterion p2^d < 1, if each random variable affects at most 3 events, the deterministic complexity of the LLL in the LOCAL model is O(d^2 + log^* n). In stark contrast, under the criterion p2^d ≤ 1, there is a randomized lower bound of Ω(loglog n) by Brandt et al. [STOC'16] and a deterministic lower bound of Ω(log n) by Chang, Kopelowitz and Pettie [FOCS'16]. Brandt, Maus and Uitto conjectured that the same behavior holds for the unrestricted setting where each random variable affects arbitrarily many events. We prove their conjecture, by providing an algorithm that solves the LLL in time O(d^2 + log^* n) under the LLL criterion p2^d < 1, which is tight in bounded-degree graphs due to an Ω(log^* n) lower bound by Chung, Pettie and Su [PODC'14]. By the work of Brandt, Maus and Uitto, obtaining such an algorithm can be reduced to proving that all members in a certain family of functions in arbitrarily high dimensions are convex on some specific domain. Unfortunately, an analytical description of these functions is known only for dimension at most 3, which led to the aforementioned restriction of their result. While obtaining those descriptions for functions of (substantially) higher dimension seems out of the reach of current techniques, we show that their convexity can be inferred by combinatorial means.

• 25 publications
• 16 publications
• 17 publications
08/17/2019

### A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovasz Local Lemma

The Lovász Local Lemma (LLL) says that, given a set of bad events that d...
03/30/2021

### The randomized local computation complexity of the Lovász local lemma

The Local Computation Algorithm (LCA) model is a popular model in the fi...
12/02/2021

### Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness

We study the complexity of optimizing highly smooth convex functions. Fo...
02/26/2019

### An Automatic Speedup Theorem for Distributed Problems

Recently, Brandt et al. [STOC'16] proved a lower bound for the distribut...
11/12/2021

### Moser-Tardos Algorithm: Beyond Shearer's Bound

In a seminal paper (Moser and Tardos, JACM'10), Moser and Tardos develop...
10/25/2021

### Parameterized Convexity Testing

In this work, we develop new insights into the fundamental problem of co...
01/09/2020

### How to trap a gradient flow

We consider the problem of finding an ε-approximate stationary point of ...

## 1 Introduction

### 1.1 Background

The Lovász Local Lemma is a celebrated result from 1975 due to Erdős and Lovász [EL75], with applications in many types of problems such as coloring, scheduling or satisfiability problems [AS08, Bec91, CPS17, CS00a, CS00b, EPS15, HSS10, LMR99, Mos09]. It states the following.

###### Lovász Local Lemma (LLL).

Let be a set of mutually independent random variables and probabilistic events that depend on the . For each , let denote the random variables depends on. We say that and share a random variable if . Assume that there is some such that for each , we have , and let be a positive integer such that each shares a random variable with at most other (where ). Then, if , there exists an assignment of values to the random variables such that none of the events occurs.111We note that the LLL criterion guaranteeing the existence of the desired variable assignment is not optimal and has been subject to improvements by Spencer [Spe77] and Shearer [She85].

The LLL can be seen as a generalization of the well-known fact that for any set of independent

events that all occur with probability strictly less than

, the probability that none of the events occurs is non-zero: some amount of dependency between the events is tolerable for preserving the avoidance guarantee—how much exactly depends on the parameter that bounds the occurrence probabilities of the events.

While being an indispensable tool for applying the probabilistic method, the LLL, in its original form, is of limited usefulness if seen from an algorithmic standpoint, as it gives a purely existential statement and does not provide a method for finding such an assignment to the random variables. The underlying algorithmic question of computing such an assignment, called the algorithmic (or constructive) LLL (problem) received considerable attention in a series of papers [Alo91, CS00a, MR98, Mos08, Mos09, Sri08], starting with Beck [Bec91] in the 90s, and culminating in a breakthrough result by Moser and Tardos [MT10] in 2010. The latter work showed that an assignment to the random variables that avoids all events can be found quickly by a simple resampling approach. Moreover, this approach is easily parallelizable, and implies a (randomized) distributed algorithm that finds the desired assignment in rounds of communication in a distributed setting w.h.p.222As usual, w.h.p. stands for “with probability at least ”. for the LLL criterion . In the following, we take a closer look at the distributed version of the algorithmic LLL, the main topic of this work.

#### The Distributed LLL

Let an instance of the LLL be given by mutually independent random variables and events satisfying some LLL criterion that guarantees existence of an assignment avoiding all events. The distributed version of the LLL is commonly phrased using the notion of the so-called dependency graph. In the dependency graph of an LLL instance, the events are the nodes, and there is an edge between two events if the two events share a variable. Each node is aware of and knows for exactly which combinations of values for the random variables in the event occurs. As before, the task is to find an assignment to the variables such that none of the events occurs. To specify the output, each node has to output a value for each variable it depends on, and any two nodes outputting a value for the same random variable have to agree on the value.

We will consider the LLL in the LOCAL model333The communication graph for the LLL is the dependency graph. For details regarding the LOCAL model, we refer to Section 2.1. of distributed computing [Lin92, Pel00], in which the LLL has been the focus of a number of important works in recent years (see Section 1.3 for an in-depth overview). One particularly intriguing result underlining the importance of the LLL was given by Chang and Pettie [CP17]: they show that any problem from a very natural problem class, called locally checkable labelings444Roughly speaking, these are problems for which the correctness of the global solution can be verified by checking the correctness of the output in the local neighborhood of each node., that has sublogarithmic randomized complexity also admits a randomized algorithm that solves it in time , where denotes the randomized complexity of the LLL under a polynomial criterion (i.e., a criterion of the form for an arbitrarily large constant ).

#### The LLL criterion

As can be expected, the complexity of solving the algorithmic LLL depends on the chosen LLL criterion. Strengthening the LLL criterion, i.e., restricting555There is some disagreement about whether this should be called a strengthening or weakening of the LLL criterion. We will use the same (sensible) terminology as the closest work to ours by Brandt, Maus and Uitto [BMU19], to make it easier to relate the results. the set of allowed LLL instances by making fewer pairs satisfy the criterion, clearly can only reduce the complexity of the LLL problem, but it is a major open question precisely how the LLL complexity relates to the chosen criterion. At which points in strengthening the LLL criterion does the asymptotic complexity of the LLL change and do we obtain smooth or sharp transitions between the different complexities?

While it is known, due to a result by Chung, Pettie and Su [CPS17], that rounds are required for any LLL criterion, the only lower bounds known so far that could possibly be used to obtain a separation between the complexities for different criteria are an lower bound for randomized algorithms by Brandt et al. [BFH16], and an lower bound for deterministic algorithms by Chang, Pettie and Kopelowitz [CKP16], which both hold even under the strong criterion . It is natural to ask whether any further strengthening of the LLL criterion breaks the lower bound or whether the lower bound can be extended to stronger criteria.

Very recently, Brandt, Maus and Uitto [BMU19] showed that if we restrict the random variables to affect at most events each (which they call rank at most ), then already under the minimally strengthened criterion , there is a deterministic LLL algorithm with a complexity of . They conjectured that this behavior also holds without their restriction on the variables.

###### Conjecture 1.1 ([Bmu19], rephrased).

There is a (deterministic) distributed algorithm that solves the LLL problem in time under the criterion .

### 1.2 Contributions and Techniques

In this work, we prove Conjecture 1.1, by providing such a deterministic algorithm. This gives a first (unrestricted) answer to the aforementioned question about the relation between the LLL criterion and the complexity of the LLL: a sharp transition occurs at the criterion , where the complexity of the LLL drops from randomized, resp.  deterministic, to . Moreover, our upper bound is tight on bounded-degree graphs due to the lower bound by Chung, Pettie and Su [CPS17]. Finally, as is the nature of upper bounds for the LLL, our result immediately implies the same upper bound for all problems that can be phrased as an LLL problem with criterion , such as certain hypergraph edge-coloring problems or orientation problems in hypergraphs (see [BMU19]).

#### Previous Techniques

Our work builds on techniques developed in [BMU19]. In their work, Brandt, Maus and Uitto obtain an -round LLL algorithm under the criterion for the case of variables of rank at most . In the following, we give an informal overview of their approach.

The basic idea of the algorithm is to go sequentially through all variables and fix them to some values one by one while preserving a certain invariant that makes sure that the final assignment avoids all events. In order to define the invariant, each edge of the dependency graph is assigned two non-negative values, one for each endpoint of the edge, that sum up to at most . When fixing a random variable, the algorithm is also allowed to change these “book-keeping” values. The invariant now states that for any node in the dependency graph, the product of the values around multiplied by is an upper bound for the conditional probability of the event associated with node to occur (where we naturally condition on the already-fixed random variables being fixed as prescribed by the (partial) value assignments performed by the algorithm so far). If this invariant is preserved, then, after all variables are fixed, each event occurs with probability at most , and therefore with probability , as desired.

Brandt, Maus and Uitto do not only show that such a sequential process preserving the invariant at all times exists (even if the order in which the random variables have to be fixed are chosen adversarially), but also that it can be made to work in a local manner: in order to fix a random variable, the algorithm only needs to know the random variables and edge values in a small local neighborhood. This allows to process random variables that affect events that are sufficiently far from each other in the dependency graph in parallel. By adding an -round preprocessing step to the algorithm where a -hop node coloring with colors is computed in the dependency graph, the sequential fixing process can then be parallelized by iterating through the color classes in a standard way, yielding the desired runtime of rounds. We will provide a more detailed overview of the algorithm from [BMU19] in Section 2.2.

The crucial, and rather surprising, observation making the algorithm work is that in each step in which a random variable is fixed, the existence of a value for that random variable that preserves the invariant is guaranteed if a certain function is shown to be convex on some domain. Hence, proving the existence of the desired algorithm is reduced to solving an analytical problem for a fixed function , providing a very intriguing connection between distributed algorithms and analysis. To be precise, Brandt, Maus und Uitto show that for any integer , there is a fixed function on some domain satisfying the following property: if is convex, then for any rank- random variable, there is a value that this variable can be fixed to such that the invariant is preserved. By proving the convexity of , they prove the desired upper bound for the case of variables of rank at most .666Taking care of the case of rank- and rank- variables is comparably easy.

One of the main problems with extending this proof to arbitrary ranks is that the function is only given in an indirect way, by a characterization of the set of points in that lie below and on the function. No closed-form expression describing is known for any , and the relatively compact form of the function for the case is arguably due to the cancellation of certain terms that do not cancel out in higher dimensions. In fact, none of the ways to obtain from the characterization of the mentioned point set seems to yield any closed-form expression if adapted to higher dimensions, and even if a closed-form expression for all were found in some way, it is far from clear that proving convexity of these functions would be feasible.

#### New Techniques

We overcome this obstacle by showing that, perhaps surprisingly, even without any analytical access to the functions , we can infer their convexity for all . In the following we give an informal overview of our approach. Our main idea is to prove convexity of —or equivalently, convexity of the set bounded by

from below— by finding a so-called locally supporting hyperplane for each point

on . More precisely, for each such

, we want to find a number of vectors such that the following two properties hold:

1. The affine subspace of spanned by the vectors and containing is a hyperplane, i.e., an affine subspace of dimension .

2. In an -ball around , the hyperplane is contained in the set consisting of all points on and below .

These properties ensure convexity of in ; however, a priori it is completely unclear how to find such vectors. In order to obtain these vectors, we consider the combinatorial description of the points on and below that is tightly connected to the aforementioned invariant: Consider a hyperedge of rank and write two non-negative values that sum up to at most on each edge of the skeleton of the hyperedge (i.e., a clique induced by the hyperedge) one value for each endpoint of the edge. For each endpoint of the hyperedge multiply the values belonging to the endpoint, and consider the -dimensional vector obtained by collecting the resulting products. The points that can be generated in this way are exactly the (non-negative) points that lie on or below .

For each such point , call the tuple of the values written on the edges that generate in the above description a generator of ; a point can have (and usually has) more than one generator. Roughly speaking, we find the desired vectors for a point by picking an arbitrary generator and, for each edge in the skeleton of the hyperedge, computing the vector by which changes if we subtract some small from one value on and add it to the other. A crucial insight is that it is fine to pick such a large set of vectors: due to the specific construction, one can show that the affine subspace spanned by these vectors and containing is -dimensional. Moreover, the redundancy contained in this choice enables us to prove Item 2 by finding, for each on the hyperplane in an -ball around , a way to write as a linear combination of of these vectors that satisfies certain desirable properties.

Note that we will use terminology that does not refer to the convexity of the function as we do not make use of this function from an analytical perspective. Instead, we will aim for the equivalent goal of showing that the set bounded by from below is convex, by making use of its combinatorial description.

### 1.3 Further Related Work

Following the resampling approach of Moser and Tardos [MT10], many of the results for the distributed LLL were based on randomized algorithms. The bounds given in the following hold w.h.p. The bound of for the algorithm by Moser and Tardos [MT10] is due to steps in which variables are resampled, where in each step a maximal independent set (MIS) is computed in rounds in order to perform the resampling in a conflict-free manner. By showing that a weaker variant of an MIS is sufficient for this purpose, Chung, Pettie and Su [CPS17] obtained an upper bound of , for the same LLL criterion . In turn, by improving the computation of such a weak MIS from to , Ghaffari [Gha16] improved this bound to .

In the aforementioned work, Chung, Pettie and Su also showed that faster algorithms can be obtained if the LLL criterion is strengthened: under the criterion , they provide an algorithm running in time , and under an exponential criterion, i.e., a criterion of the form where is exponential in , they give an upper bound of . For LLL instances with , Fischer and Ghaffari [FG17] provided a -round algorithm under the criterion . Ghaffari, Harris and Kuhn [GHK18] improved on this result by showing that for any integer , there is an LLL algorithm running in time under the criterion , where and represent a power tower and the iterated logarithm, respectively. Finally, Rozhon and Ghaffari [RG20] proved, as one of the many implications of their recent breakthrough in computing network decompositions, that on bounded-degree graphs a variable assignment avoiding all events can be found in rounds under the criterion , closing in on a conjecture by Chang and Pettie [CP17] stating that rounds are sufficient.

The latter three works [FG17, GHK18, RG20] also provide the first non-trivial deterministic algorithms for the distributed LLL. The currently best known upper bound by Rozhon and Ghaffari [RG20] (for polynomial criteria) states that rounds suffice under the criterion , for any constant .

## 2 Preliminaries

### 2.1 Model

The model in which we study the LLL is the LOCAL model of distributed computing [Lin92, Pel00]. In the LOCAL model, we usually want to solve a graph problem, but unlike in centralized computation, the actual computation is performed by the nodes of the input graph. To this end, each node of the input graph is considered as a computational entity, and each edge as a communication link over which the entities can communicate. The computation proceeds in synchronous rounds, where in each round two things happen: first, each node sends an arbitrarily large message to each of its neighbors and then, after the messages have arrived, each node can perform an arbitrarily complex internal computation. Each node has to decide at some point that it terminates and then it must output its local part of the global solution to the given problem—in the case of the LLL problem this local part is the values of all random variables the associated event depends on. The runtime of a distributed algorithm is the number of rounds until the last node terminates.

### 2.2 The Reduction

In this section, we will give a detailed explanation of the argumentation presented in [BMU19] that reduces proving the existence of an -round distributed deterministic LLL algorithm under the criterion to showing that a certain family of sets or functions is convex. The blueprint for such an algorithm is given as follows.

Consider an instance of the LLL, given by a set of mutually independent random variables and a set of events that depend on the random variables. Consider the dependency graph of this instance, and denote the event associated with a vertex by , and the maximum degree of by . Let be a parameter such that each event occurs with probability at most , and assume that , i.e., fix the LLL criterion to . As any two events that depend on the same variable are neighbors of each other in , we can create for each random variable a hyperedge that has the nodes such that depends on as endpoints. Technically, the hyperedges are not part of , but for simplicity, we might consider them as such.

Algorithm starts by computing a -hop coloring with colors in rounds, by applying the coloring algorithm by Fraigniaud, Heinrich and Kosowski [FHK16] to , i.e., to the graph obtained by connecting any two nodes of distance at most in by an edge. Then, it iterates through the colors one by one, and each time a color is processed, each node of color fixes each incident random variable (i.e., each random variable whose corresponding hyperedge is incident to ) that has not been fixed so far. We will see that in order to fix all incident random variables of a node in a suitable way, rounds suffice, and as there are colors, algorithm runs in rounds.

The challenging part is to fix the random variables in a manner such that the produced final assignment is correct, i.e., such that none of the events occurs under the assignment. To this end, during the fixing process the authors keep track of, roughly speaking, how favorable or unfavorable the variable fixings performed so far were for the nodes (regarding avoiding the associated event), by assigning two values to each edge. More precisely, they assign a non-negative value to each pair for which is incident to . We can imagine the two values and to be written on edge ; each time a random variable is fixed by a node, the node also updates the values that are written on the edges in the skeleton of the hyperedge corresponding to .

The purpose of these edge values w.r.t. obtaining a correct output in the end of the process is to define a property that is kept as an invariant during the fixing process and guarantees that the final assignment avoids all events. Consider an arbitrary point in the fixing process where some random variables already have been fixed to some values , respectively. Property is satisfied if the following two conditions hold.

1. for each edge .

2. for each node .

If Property is satisfied when all variables have been fixed, then for each event we have a bound of for the probability that occurs, which implies that does not occur since the probability of it occurring can only be or . By initializing each value to , the authors make sure that is satisfied when algorithm starts. The crucial insight in [BMU19] is that there is always a way to preserve Property each time a random variable is fixed if a certain function or set is convex. For the precise statement, the authors introduce the notion of a representable triple.

###### Definition 2.1 (Definition 3.3 of [Bmu19]).

A triple is called representable if there are values such that , , , , , and . Let denote the set of all representable triples.

Using this definition, the authors prove the following statement for the case of rank- random variables (which we give in a reformulated version using the notion of convexity instead of the concept of “incurvedness” used in [BMU19]).

If is a convex set, then there is a way to fix any given random variable of rank at most at any point in time during the algorithm (or, more generally, for any arbitrary fixing of already fixed random variables such that Property is satisfied) such that Property is preserved. Moreover, the only information required to fix is the set of values written on the edges that belong to the skeleton of the hyperedge corresponding to . We refer to [BMU19, Section 3.3] for the details of the proof.

Hence, in algorithm , each node that has the task to fix all its incident unfixed random variables can simply collect all edge values written on edges between nodes in its inclusive -hop neighborhood, and then go through its incident random variables one by one, each time finding a value for the random variable in question that preserves Property . As the sequential fixing does not require any communication after obtaining the required edge values, fixing all incident unfixed variables of a node can be done in rounds. Moreover the local nature of and the fact that the set of edge values required and rewritten by a node during the fixing does not intersect with the set of analogous edge values for a node in distance at least ensures that any two nodes with the same color in the computed -hop coloring can perform the variable fixing in parallel. This concludes the description of the reduction.

As already noted by the authors, the definitions and proofs (for the reduction to the convexity statement) generalize straightforwardly to the case of random variables of arbitrary rank. However, showing that the convexity of the respective set indeed holds for higher dimensions remained unanswered in [BMU19]; and indeed, even given our resolution, it remains unclear and would be interesting to see whether their analytical approach can feasibly be extended to higher dimensions than . To be precise, their approach extends in the following way: to prove the existence of the deterministic algorithm in the case that each random variable affects at most events, it suffices to prove that the set is convex, where is the set of all representable tuples, which are tuples that can be generated by some generator, as defined below.

###### Definition 2.2 (generator).

We call a vector with coordinates a generator if for each we have and . The generator generates the -dimensional tuple with for . We call a generator non-zero, if none of its coordinates is . We use a shorthand notation and denote the generator simply as .

Note that if is a non-zero generator, then for each .

###### Definition 2.3 (representable tuples).

A tuple is called representable if there exists a generator that generates it. Let denote the set of all representable tuples.

Note that , as we require instead of . We consider this scaled version, as this makes the proof cleaner later on: note that being convex directly implies that is convex as the latter is just a scaled variant of the former set. In the following, we drop the superscripts when clear from context and we denote with the set of representable tuples with respect to the scaled down version and as the set of points in which are not representable. Our main contribution is the proof of the following theorem.

###### Theorem 2.4.

For every , is convex.

This settles Conjecture 1.1 as described above.

## 3 Proving that Snon is convex

In this section we prove that set is convex, omitting two longer proofs that are postponed to Section 4 and Section 5.

### 3.1 Notation

We work with the standard Euclidean space where distances are measured with the Euclidean norm; 0 and 1 denote the vectors and , respectively. We define as the closed ball around with radius . A subset is open if for any , there exists such that . A subset is closed if is open. A set is bounded if there exists such that . A set is compact if it is closed and bounded. Equivalently, is compact if every sequence with each has a subsequence that converges to some . The subset is compact. The interior of a set is an open subset of and defined as . The boundary of a set is defined as . A set is path-connected if for any there exists a continuous function such that and .

A hyperplane is an affine subspace of dimension . Equivalently, it is a set of points for some vector and . A weakly supporting hyperplane for intersecting is a hyperplane with and for any . Finally, a weakly locally supporting hyperplane for intersecting is a hyperplane with satisfying the following property: there exists an such that for any we have .

### 3.2 Proof

Convexity of a set can be verified in several equivalent ways. As we outlined in Section 1.2, we rely on the “supporting hyperplane formulation”, i.e., a set is convex if for each boundary point we can find a hyperplane such that the whole set lies on one side of the hyperplane. Moreover, for connected sets, it is enough to prove that each such hyperplane is “locally” supporting as formalized in the following theorem, which is stated in a more general form in [Val75] (Theorem 4.10 there).

###### Theorem 3.1.

Let be an open and path-connected set in . The set is convex if for every point contained in the boundary of , there exists a weakly locally supporting hyperplane with respect to going through .

Note that Theorem 3.1 can only be used to prove convexity of open sets and thus cannot directly applied to establish the convexity of . Instead, we use Theorem 3.1 to first establish convexity of the interior of , which is an open set and which we denote by . Once we have established the convexity of , we prove the convexity of by induction on the dimension . To prove convexity of , we need to show that is path-connected and that for every boundary point of , there exists a weakly locally supporting hyperplane going through the boundary point. We now prove the former, using the following simple observation, which will be used in several other proofs.

###### Observation 3.2.

Let be a representable tuple. Then any tuple with for all is also representable.

###### Proof.

Consider a generator of . For any , pick some and set . Set all other values in equal to the corresponding value in . is a valid generator generating the tuple . ∎

Now, we are ready to prove that is path-connected.

###### Lemma 3.3.

The set is path-connected.

###### Proof.

For any , consider the vector with for every . Note that the union of the two segments between and and between and is a path. Moreover, any tuple on this path is contained in and either dominates or . Hence, by Observation 3.2, each tuple on the path is in . ∎

Next, we need to understand the boundary between and . To do so, it will be helpful to prove that is closed. As is bounded, this is equivalent to show that is compact.

###### Lemma 3.4.

The set is compact.

###### Proof.

The set is defined as an image of a continuous function that maps each generator (Definition 2.2) from the compact set of all generators to the corresponding representable tuple. Hence, it is compact as an image of a compact set under continuous function is always compact. ∎

Next, we set up the notion of maximal tuples.

###### Definition 3.5 (domination and maximal tuples).

Let and be two representable tuples. We say that weakly dominates if for all , and . Moreover, we say that strongly dominates if for all . We call a representable tuple maximal if there is no representable tuple that weakly dominates .

Intuitively, maximal tuples are forming the boundary between and and this is indeed what we prove.

###### Lemma 3.6.

Let be contained in . Then, there either exists such that or is a maximal representable tuple.

We defer the easy, yet slightly technical proof, together with proofs of a few other technical lemmas, to Section 4. Our main technical contribution is a proof that a locally supporting hyperplane can be found for any maximal tuple .

###### Lemma 3.7.

For each maximal representable tuple , there exists a locally supporting hyperplane for intersecting .

The non-trivial proof of the above lemma is deferred to Section 5. As a corollary, we infer that the whole set is convex.

###### Corollary 3.8.

The set is convex.

###### Proof.

By Theorem 3.1 it suffices to provide a weakly locally supporting hyperplane for any . By Lemma 3.6, any is either a maximal representable tuple and hence the existence of the supporting hyperplane follows from Lemma 3.7, or we have or , respectively, for some . But then the hyperplane or , respectively, is a weakly (locally) supporting hyperplane for intersecting . ∎

The proof of Theorem 2.4 now easily follows.

###### Proof of Theorem 2.4.

We prove the statement by induction on . For , the statement trivially holds. Now, let arbitrary and assume that is convex. Let and be arbitrary. We need to show that for we have . As is a closed set (Lemma 3.4), there exists some with such that and, hence, since the whole segment is contained in , and . Furthermore, there exists an such that .

If , then, by Corollary 3.8, it follows that and we are done. Otherwise, or . Without loss of generality, assume that . Since , Lemma 3.6 implies that there exists some with . Our choice of now implies that either or .

In the first case, as is not representable, there exists some with . Therefore, and as , any generator of would need to have and , a contradiction with . Hence, .

In the second case, assume without loss of generality that . Let , , be equal to the vectors , and restricted to the first coordinates. We have , since otherwise taking their generator and augmenting it by zeros would generate or , respectively. As is a convex combination of and , the induction hypothesis implies that and therefore , which concludes the induction step. ∎

## 4 Technical preparation

In this section we prove several technical results that are needed for the proof. First, we prove the equivalence of the notions of weak and strong dominance. To this end, we first show a simple “continuity” statement that shows that for any representable tuple , one can increase all but one of its coordinates a little bit at the expense of decreasing the remaining one.

###### Lemma 4.1.

Let be a representable tuple with for each . For each , there exist an and a such that for all with , the tuple defined by and for is also representable.

###### Proof.

Let be a generator of . As for each , is a non-zero generator. Now, for some , consider with

 bij=⎧⎪⎨⎪⎩aij−δ if i=kaij+δ if j=kaij otherwise

for each . We have for each . Furthermore, if we choose such that , we have for each . In that case, is a valid generator that generates a tuple such that:

 bk=∏j≠kbkj=∏j≠k(akj−δ)≥⎛⎝∏j≠kakj⎞⎠−δf((aij))=ak−δf((aij))

for some function with . Note that such a function exists, as and therefore for each . For each , we have:

 bi =∏j≠ibij=(aik+δ)⋅∏j∉{i,k}aij=ai+δ⋅∏j∉{i,k}aij ≥ai+δ⋅∏j≠iaij=ai+δai

Set , and . Now, consider some arbitrary with . The definition of implies that . Thus, we can represent a tuple with and for . This tuple dominates the tuple . As for each , Observation 3.2 implies that we can represent . ∎

Now we are ready to show that if a tuple is weakly dominated by some other tuple, it is also strongly dominated by (a potentially different) one.

###### Corollary 4.2 (strong vs weak domination).

Let be a representable tuple such that for all we have . If there exists a representable tuple that weakly dominates , then there also exists a representable tuple that strongly dominates .

###### Proof.

Let be a representable tuple that weakly dominates . Note that we have for each . Let such that . According to Lemma 4.1, there exists and such that for all , the tuple is representable. For small enough, this tuple strictly dominates the tuple . ∎

We are now ready to prove Lemma 3.6.

###### Proof of Lemma 3.6.

We show the contrapositive. Let such that for each and is not a maximal representable tuple. We show that this implies the existence of a ball around with radius such that either or , which in turn implies .

For there is clearly such a ball. Otherwise, we have , as we assume that for each , . If , but is not maximal representable, there is a representable tuple that weakly dominates and as , Corollary 4.2 provides a representable tuple that strongly dominates . Hence, there exists some such that the tuple is a representable tuple. This implies that for we have due to Observation 3.2 and, hence, as needed. Finally, in the case Lemma 3.4 implies that the complement of is open which in turn implies the existence of an so that . For we then have , as needed. ∎

## 5 Construction of hyperplanes

In this section we prove our main technical contribution: Lemma 3.7 that states that for each maximal tuple we can find a locally weakly supporting hyperplane for the set . First, we give an informal proof of this result for the case , which captures the intuition behind the general proof for all that we give later.

### 5.1 Informal outline for r=3

Our main observation is that finding a locally supporting hyperplane comes down to proving that a certain set of tuples in the neighbourhood of is representable. In this section, we denote the tuples, more intuitively, as triples. So, we now focus on how to generate triples similar to .

#### Generating more triples

Given a representable triple generated by the generator , what other triples close to are representable? Certainly, all the triples that dominates. Besides, we can play with the generator itself. Adding to and subtracting it from gives us again a valid generator that generates triples of the form

 (a13(a12+α12),(a21−α12)a23,a31a32)=a+α12(a13,−a23,0)

I.e., it generates triples on the line

 a+α12(a13,−a23,0)=a+α12w12,α12∈R

for small enough. Similarly, by adding to and subtracting it from , we can generate triples on the line

 a+α13(a12,0,−a32)=a+α13w13,α13∈R

and by adding to and subtracting it from , we can generate triples on the line

 a+α23(0,a21,−a31)=a+α23w23,α23∈R

in some neighborhood around the triple . We call the three lines and .

Since all components of the generator of are nonzero, these three lines define an affine subspace of dimension at least two. Later we prove that if is a maximal representable triple, then the three lines lie on a common plane. The plane spanned by and then becomes an obvious suspect for the supporting hyperplane we wish to find!

In fact, we prove that not only triples on the lines and are representable, given that they lie in some small neighborhood around the maximal representable triple , but any triple in the affine span of the three lines is representable, provided that for some positive that depends on . This finishes our proof, as we can now find a weakly locally supporting hyperplane for each maximal representable triple .

We now prove that for maximal triples all three lines lie in a common plane and all triples in that plane are representable (if they are close enough to ).

###### Claim 5.1.

For a maximal triple , the affine hull of and is a plane.

Assume the contrary. Then, there exist , such that . Now, change the values of proportional to the values of to obtain the generator with

 a′12 =a12+ξα12,a′21=a21−ξα12; a′13 =a13+ξα13,a′31=a31−ξα13; a′23 =a23+ξα23,a′32=a32−ξα23.

Intuitively, we expect these changes to give us a generator of . This is almost the case:

 a′ =(a′12a′13,a′21a′23,a′31a′32) =((a12+ξα12)(a13+ξα13),(a21−ξα12)(a23+ξα23), (a31−ξα13)(a32−ξα23)) =(a12a13,a21a23,a31a32)+ξα12(a13,−a23,0) +ξα13(a12,0,−a32)+ξα23(0,a21,−a31) +ξ2(α12α13,−α12α23,α13α23) =a+ξα12w12+ξα13w13+ξα23w23 +ξ2(α12α13,−α12α23,α13α23) =a+ξ(1,1,1)+ξ2(α12α13,−α12α23,α13α23)

Choosing small enough, we conclude that the triple is representable and therefore is not maximal, a contradiction!

#### Generating triples on the plane

We are given a maximal triple and some in the affine hull of and that is sufficiently close to . We need to prove that is representable. To do so, we first note that as is contained in the affine hull, there exist and such that


text:
We have isolated a stable mutant of CHO cells, designated irs-20, that is hypersensitive to ionizing radiation. The selection system was designed to select for mutants unable to proliferate at the low dose rate of 0.06 Gy per hour, a dose rate that has little influence on the effect of radiation on the cell cycle of wild-type cells during 1- to 2-week exposures. The irs-20 mutant cells irradiated continuously at 0.06 Gy/h showed a cell cycle redistribution, with an increasing <tex-math>${\rm G}_{2}+{\rm M}\text{-phase}$</tex-math> fraction, but underwent approximately four doublings before cell population growth was completely inhibited. Dose rates three to four times higher were required to produce similar perturbation in the cell cycle of wild-type cells. Asynchronous log-phase irs-20 cells were approximately twofold more sensitive than the parental CHO cells as measured by comparing the doses required to reduce survival to 10%. The survival response of synchronized irs-20 cells after a single radiation dose of 3.8 Gy at different times during the cell cycle was qualitatively similar to the pattern for wild-type CHO cells for an approximately isosurvival dose of 7.4 Gy. The irs-20 cells were hypersensitive to the "radiomimetic" drug bleomycin but showed the wild-type sensitivity to ethyl methane sulfonate, ultraviolet light (254 nm) and mitomycin C. The irs-20 mutant cell has maintained its phenotype for over 1 year in continuous culture, indicating that the defect is genetically stable. The karyotype of the mutant cells is not different from that of its parent. Further evidence of stability is that clonal lines derived from cells surviving high radiation doses also had the irs-20 phenotype, and treatments with 5-azacytidine sufficient to cause high reversion (<tex-math>$\sim 2\times 10^{-1}$</tex-math>) to proline independence resulted in no measurable reversion to wild-type radiosensitivity.

This content is only available as a PDF.


text:
# American Institute of Mathematical Sciences

July  2003, 9(4): 937-948. doi: 10.3934/dcds.2003.9.937

## Spatially periodic equilibria for a non local evolution equation

 1 Instituto de Matemática e Estatística, Universidade de São Paulo, R. do Matão 1010, 05508-900, S. Paulo, Brazil, Brazil, Brazil, Brazil

Received  November 2001 Revised  December 2002 Published  April 2003

In this work we prove the existence of a global attractor for the non local evolution equation $\frac { \partial m ( r , t ) } { \partial t } = - m ( r , t ) + \tanh ( \beta J$*$m ( r , t ) )$ in the space of $\tau$-periodic functions, for $\tau$ sufficiently large. We also show the existence of non constant (unstable) equilibria in these spaces.
Citation: Saulo R.M. Barros, Antônio L. Pereira, Cláudio Possani, Adilson Simonis. Spatially periodic equilibria for a non local evolution equation. Discrete and Continuous Dynamical Systems, 2003, 9 (4) : 937-948. doi: 10.3934/dcds.2003.9.937
 [1] Qi Wang, Ling Jin, Zengyan Zhang. Global well-posedness, pattern formation and spiky stationary solutions in a Beddington–DeAngelis competition system. Discrete and Continuous Dynamical Systems, 2020, 40 (4) : 2105-2134. doi: 10.3934/dcds.2020108 [2] Rong Chen, Shihang Pan, Baoshuai Zhang. Global conservative solutions for a modified periodic coupled Camassa-Holm system. Electronic Research Archive, 2021, 29 (1) : 1691-1708. doi: 10.3934/era.2020087 [3] Zonglin Jia, Youde Wang. Global weak solutions to Landau-Lifshtiz systems with spin-polarized transport. Discrete and Continuous Dynamical Systems, 2020, 40 (3) : 1903-1935. doi: 10.3934/dcds.2020099 [4] Zhirong He, Weinian Zhang. Critical periods of a periodic annulus linking to equilibria at infinity in a cubic system. Discrete and Continuous Dynamical Systems, 2009, 24 (3) : 841-854. doi: 10.3934/dcds.2009.24.841 [5] Jérôme Coville, Juan Dávila. Existence of radial stationary solutions for a system in combustion theory. Discrete and Continuous Dynamical Systems - B, 2011, 16 (3) : 739-766. doi: 10.3934/dcdsb.2011.16.739 [6] Sergiu Aizicovici, Hana Petzeltová. Convergence to equilibria of solutions to a conserved Phase-Field system with memory. Discrete and Continuous Dynamical Systems - S, 2009, 2 (1) : 1-16. doi: 10.3934/dcdss.2009.2.1 [7] Marilena N. Poulou, Nikolaos M. Stavrakakis. Global attractor for a Klein-Gordon-Schrodinger type system. Conference Publications, 2007, 2007 (Special) : 844-854. doi: 10.3934/proc.2007.2007.844 [8] Francesca Bucci, Igor Chueshov, Irena Lasiecka. Global attractor for a composite system of nonlinear wave and plate equations. Communications on Pure and Applied Analysis, 2007, 6 (1) : 113-140. doi: 10.3934/cpaa.2007.6.113 [9] Olivier Goubet, Manal Hussein. Global attractor for the Davey-Stewartson system on $\mathbb R^2$. Communications on Pure and Applied Analysis, 2009, 8 (5) : 1555-1575. doi: 10.3934/cpaa.2009.8.1555 [10] Jia-Cheng Zhao, Zhong-Xin Ma. Global attractor for a partly dissipative reaction-diffusion system with discontinuous nonlinearity. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022103 [11] Carlos J. Garcia-Cervera, Xiao-Ping Wang. Spin-polarized transport: Existence of weak solutions. Discrete and Continuous Dynamical Systems - B, 2007, 7 (1) : 87-100. doi: 10.3934/dcdsb.2007.7.87 [12] Caixia Chen, Shu Wen. Wave breaking phenomena and global solutions for a generalized periodic two-component Camassa-Holm system. Discrete and Continuous Dynamical Systems, 2012, 32 (10) : 3459-3484. doi: 10.3934/dcds.2012.32.3459 [13] Daniel Ginsberg, Gideon Simpson. Analytical and numerical results on the positivity of steady state solutions of a thin film equation. Discrete and Continuous Dynamical Systems - B, 2013, 18 (5) : 1305-1321. doi: 10.3934/dcdsb.2013.18.1305 [14] Ning Ju. The global attractor for the solutions to the 3D viscous primitive equations. Discrete and Continuous Dynamical Systems, 2007, 17 (1) : 159-179. doi: 10.3934/dcds.2007.17.159 [15] Yukio Kan-On. Global bifurcation structure of stationary solutions for a Lotka-Volterra competition model. Discrete and Continuous Dynamical Systems, 2002, 8 (1) : 147-162. doi: 10.3934/dcds.2002.8.147 [16] V. Barbu. Periodic solutions to unbounded Hamiltonian system. Discrete and Continuous Dynamical Systems, 1995, 1 (2) : 277-283. doi: 10.3934/dcds.1995.1.277 [17] Luca Battaglia. A general existence result for stationary solutions to the Keller-Segel system. Discrete and Continuous Dynamical Systems, 2019, 39 (2) : 905-926. doi: 10.3934/dcds.2019038 [18] M. Grasselli, Hana Petzeltová, Giulio Schimperna. Convergence to stationary solutions for a parabolic-hyperbolic phase-field system. Communications on Pure and Applied Analysis, 2006, 5 (4) : 827-838. doi: 10.3934/cpaa.2006.5.827 [19] Francesco Paparella, Alessandro Portaluri. Geometry of stationary solutions for a system of vortex filaments: A dynamical approach. Discrete and Continuous Dynamical Systems, 2013, 33 (7) : 3011-3042. doi: 10.3934/dcds.2013.33.3011 [20] Sabri Bensid, Jesús Ildefonso Díaz. Stability results for discontinuous nonlinear elliptic and parabolic problems with a S-shaped bifurcation branch of stationary solutions. Discrete and Continuous Dynamical Systems - B, 2017, 22 (5) : 1757-1778. doi: 10.3934/dcdsb.2017105

2020 Impact Factor: 1.392


text:
## Functions Modeling Change: A Preparation for Calculus, 5th Edition

$$\sqrt{\frac{3}{2}}$$
Finding the exact value using the Laws of Trigonometry, we obtain: $$2\cos \left(45^{\circ \:}\right)\cos \left(30^{\circ \:}\right) \\ 2\cdot \frac{\sqrt{2}}{2}\cdot \frac{\sqrt{3}}{2} \\ \sqrt{\frac{3}{2}}$$