Skip to content

Instantly share code, notes, and snippets.

@kalmarek

kalmarek/Positivity of Adj_n + kOp_n in ISL(n,Z).ipynb

Last active July 5, 2019 21:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kalmarek/03510181bc1e7c98615e86e1ec580b2a to your computer and use it in GitHub Desktop.
Save kalmarek/03510181bc1e7c98615e86e1ec580b2a to your computer and use it in GitHub Desktop.
Download ZIP
Positivity of Adj_n + kOp_n in ISL(n,Z)
Display the source blob
Display the rendered blob
Raw
Positivity of Adj_n + kOp_n in ISL(n,Z).ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"cell_style": "center"
},
"source": [
"# Installation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following instructions were prepared using `julia-1.1.1`.\n",
"\n",
"----\n",
"\n",
"Before exploring the notebook you need to clone the main repository:\n",
"```bash\n",
" git clone https://github.com/kalmarek/1812.03456.git\n",
"```\n",
"This notebook should be located in `1812.03456/notebooks` directory.\n",
"\n",
"In the main directory (`1812.03456`) you should run the following code in `julia`s `REPL` console to instantiate the environment for computations:\n",
"```julia\n",
"using Pkg\n",
"Pkg.activate(\".\")\n",
"Pkg.instantiate()\n",
"```\n",
"(this needs to be done once per installation).\n",
"\n",
"Instantiation should install (among others): the [`SCS` solver][1], [`JuMP` package][2] for mathematical programming and `IntervalArithmetic.jl` package from [`ValidatedNumerics.jl`][3].\n",
"\n",
"The environment uses [`Groups.jl`][7], [`GroupRings.jl`][6] (which are built on the framework of [`AbstractAlgebra.jl`][4]) and [`PropertyT.jl`][8] packages.\n",
"\n",
"[1]: https://github.com/cvxgrp/scs \n",
"[2]: https://github.com/JuliaOpt/JuMP.jl \n",
"[3]: https://github.com/JuliaIntervals/ValidatedNumerics.jl\n",
"[4]: https://github.com/Nemocas/AbstractAlgebra.jl\n",
"[5]: https://github.com/Nemocas/Nemo.jl\n",
"[6]: https://github.com/kalmarek/GroupRings.jl\n",
"[7]: https://github.com/kalmarek/Groups.jl\n",
"[8]: https://github.com/kalmarek/PropertyT.jl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# The computation\n",
"\n",
"The following programme certifies that\n",
"$$\\operatorname{Adj}_4 + \\operatorname{Op}_4 - 0.82\\Delta_4 =\\Sigma_i \\xi_i^*\\xi_i \\in \\Sigma^2_2\\mathbb{R}\\operatorname{SL}(4,\\mathbb{Z}).$$\n",
"\n",
"With small changes (which we will indicate) it also certifies that \n",
"$$\\operatorname{Adj}_3 - 0.157999\\Delta_3 \\in \\Sigma^2_2\\mathbb{R}\\operatorname{SL}(3,\\mathbb{Z})$$\n",
"and that\n",
"$$\\operatorname{Adj}_5 +1.5 \\mathrm{Op}_5 - 1.5\\Delta_5 \\in \\Sigma^2_2\\mathbb{R}\\operatorname{SL}(5,\\mathbb{Z}).$$"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:42:42.490000+02:00",
"start_time": "2019-07-05T20:42:36.687Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"2019-07-05T22:42:41.473"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"using Pkg\n",
"Pkg.activate(\"..\")\n",
"using Dates\n",
"now()"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:42:48.528000+02:00",
"start_time": "2019-07-05T20:42:36.706Z"
},
"scrolled": true
},
"outputs": [],
"source": [
"using LinearAlgebra\n",
"using AbstractAlgebra\n",
"using Groups\n",
"using GroupRings\n",
"using PropertyT"
]
},
{
"cell_type": "markdown",
"metadata": {
"ExecuteTime": {
"end_time": "2018-11-24T12:10:28.877000+01:00",
"start_time": "2018-11-24T11:10:27.729Z"
}
},
"source": [
"So far we only made the needed packages available in the notebook. \n",
"In the next cell we define `G` to be the set of all $4\\times 4$ matrices over $\\mathbb Z$.\n",
"(For the second computation, set `N=3` below; for the third, set `N=5`)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:42:51.440000+02:00",
"start_time": "2019-07-05T20:42:36.729Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"Matrix Algebra of degree 4 over Integers"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"N = 4\n",
"G = MatrixAlgebra(zz, N)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Generating set\n",
"Now we create the elementary matrices $E_{i,j}$. The set of all such matrices and their inverses is denoted by `S`."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:42:53.534000+02:00",
"start_time": "2019-07-05T20:42:36.741Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"24-element Array{AbstractAlgebra.Generic.MatAlgElem{Int64},1}:\n",
" [1 1 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] \n",
" [1 0 1 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] \n",
" [1 0 0 1]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] \n",
" [1 0 0 0]\n",
"[1 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] \n",
" [1 0 0 0]\n",
"[0 1 1 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] \n",
" [1 0 0 0]\n",
"[0 1 0 1]\n",
"[0 0 1 0]\n",
"[0 0 0 1] \n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[1 0 1 0]\n",
"[0 0 0 1] \n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 1 1 0]\n",
"[0 0 0 1] \n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 1]\n",
"[0 0 0 1] \n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[1 0 0 1] \n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 1 0 1] \n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 1 1] \n",
" [1 -1 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1]\n",
" [1 0 -1 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1]\n",
" [1 0 0 -1]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1]\n",
" [1 0 0 0]\n",
"[-1 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1]\n",
" [1 0 0 0]\n",
"[0 1 -1 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1]\n",
" [1 0 0 0]\n",
"[0 1 0 -1]\n",
"[0 0 1 0]\n",
"[0 0 0 1]\n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[-1 0 1 0]\n",
"[0 0 0 1]\n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 -1 1 0]\n",
"[0 0 0 1]\n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 -1]\n",
"[0 0 0 1]\n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[-1 0 0 1]\n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 -1 0 1]\n",
" [1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 -1 1]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"S = PropertyT.generating_set(G)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Group Ring and Laplacians\n",
"Now we will generate the ball `E_R` of radius $R=4$ in $\\operatorname{SL}(N,\\mathbb{Z})$ and use this as a (partial) basis in a group ring (denoted by `RG` below). Such group ring also needs a multiplication table (`pm`, which is actually a *division table*) which is created as follows: when $x,y$ reside at positions `i`-th and `j`-th in `E_R`, then `pm[i,j] = k`, where `k` is the position of $x^{-1}y$ in `E_R`. "
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:42:56.762000+02:00",
"start_time": "2019-07-05T20:42:36.774Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"sizes = [25, 433, 6149, 75197]\n"
]
},
{
"data": {
"text/plain": [
"24[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 1 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 1 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 1]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[1 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 1 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 1]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[1 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 1 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 1]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[1 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 1 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 1 1] - 1[1 -1 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 -1 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 -1]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[-1 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 -1 0]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 -1]\n",
"[0 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[-1 0 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 -1 1 0]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 -1]\n",
"[0 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[-1 0 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 -1 0 1] - 1[1 0 0 0]\n",
"[0 1 0 0]\n",
"[0 0 1 0]\n",
"[0 0 -1 1]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"halfradius = 2\n",
"E_R, sizes = Groups.generate_balls(S, radius=2*halfradius);\n",
"E_rdict = GroupRings.reverse_dict(E_R)\n",
"pm = GroupRings.create_pm(E_R, E_rdict, sizes[halfradius]; twisted=true);\n",
"RG = GroupRing(G, E_R, E_rdict, pm)\n",
"@show sizes;\n",
"Δ = length(S)*one(RG) - sum(RG(s) for s in S)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Orbit Decomposition\n",
"Now something happens: in the next cell we split the subspace of $\\mathbb{R} \\operatorname{SL}(N, \\mathbb{Z})$ supported on `E_R` into irreducible representations of the wreath product $\\mathbb Z / 2 \\mathbb Z \\wr \\operatorname{Sym}_N$. The action of wreath product on the elements of the matrix space is by conjugation, i.e. permutation of rows and columns.\n",
"We also compute projections on the invariant subspaces to later speed up the optimisation step."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:12.391000+02:00",
"start_time": "2019-07-05T20:42:36.813Z"
}
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"┌ Info: Decomposing basis of RG into orbits of\n",
"│ autS = Wreath Product of Permutation group over 2 elements by Permutation group over 4 elements\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:15\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 0.381708 seconds (1.18 M allocations: 82.083 MiB, 6.45% gc time)\n"
]
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"┌ Info: The action has 558 orbits\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:18\n",
"┌ Info: Finding projections in the Group Ring of\n",
"│ autS = Wreath Product of Permutation group over 2 elements by Permutation group over 4 elements\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:20\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 6.154452 seconds (9.74 M allocations: 487.622 MiB, 4.69% gc time)\n"
]
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"┌ Info: Finding AutS-action matrix representation\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:23\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 0.294136 seconds (963.71 k allocations: 64.184 MiB, 6.98% gc time)\n",
" 0.440521 seconds (717.96 k allocations: 49.094 MiB, 4.87% gc time)\n"
]
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"┌ Info: Computing the projection matrices Uπs\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:27\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1.778654 seconds (1.75 M allocations: 841.323 MiB, 5.12% gc time)\n"
]
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"┌ Info: \n",
"│ multiplicities = 3 13 19 12 10 0 0 0 9 11 13 15 0 0 0 1 1 1 2 1\n",
"│ dimensions = 1 3 3 2 1 4 8 4 6 6 6 6 4 8 4 1 3 3 2 1\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:37\n",
"┌ Info: Sparsifying (433, 3)-matrix... \n",
"│ 0.7013086989992302 → 0.18475750577367206 ), (240 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 13)-matrix... \n",
"│ 0.5821637946349263 → 0.3084029134837449 ), (1736 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 19)-matrix... \n",
"│ 0.6031360155585268 → 0.4934970220007293 ), (4060 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 12)-matrix... \n",
"│ 0.6123941493456505 → 0.2817551963048499 ), (1464 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 10)-matrix... \n",
"│ 0.48221709006928404 → 0.1 ), (433 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 9)-matrix... \n",
"│ 0.24044136515268155 → 0.03695150115473441 ), (144 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 11)-matrix... \n",
"│ 0.19462523619567498 → 0.033592273777031285), (160 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 13)-matrix... \n",
"│ 0.16237342334340024 → 0.02842423165748801 ), (160 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 15)-matrix... \n",
"│ 0.16874518860662047 → 0.027097767513471902), (176 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 1)-matrix... \n",
"│ 0.11085450346420324 → 0.11085450346420324 ), (48 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 1)-matrix... \n",
"│ 0.07390300230946882 → 0.07390300230946882 ), (32 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 1)-matrix... \n",
"│ 0.07390300230946882 → 0.07390300230946882 ), (32 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 2)-matrix... \n",
"│ 0.11200923787528869 → 0.09237875288683603 ), (80 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n",
"┌ Info: Sparsifying (433, 1)-matrix... \n",
"│ 0.11085450346420324 → 0.11085450346420324 ), (48 non-zeros)\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/orbitdata.jl:114\n"
]
}
],
"source": [
"od = PropertyT.OrbitData(RG, WreathProduct(PermGroup(2), PermGroup(N)))\n",
"orbit_data = PropertyT.decimate(od);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Elements Adj and Op\n",
"Now we define the elements $\\operatorname{Adj}_N$ and $\\operatorname{Op}_N$. The functions `Sq`, `Adj`, `Op` returning the appropriate elements are defined in the `src/sqadjop.jl` source file."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:14.401000+02:00",
"start_time": "2019-07-05T20:42:36.826Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1.719218 seconds (2.70 M allocations: 134.807 MiB, 3.24% gc time)\n",
" 0.284995 seconds (367.56 k allocations: 18.374 MiB, 2.55% gc time)\n"
]
}
],
"source": [
"@time AdjN = PropertyT.Adj(RG, N)\n",
"@time OpN = PropertyT.Op(RG, N);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally we compute the element `elt` of our interest:\n",
"* if `N=3`: $\\operatorname{elt} = \\operatorname{Adj}_3$\n",
"* if `N=4`: $\\operatorname{elt} = \\operatorname{Adj}_4 + \\operatorname{Op}_4$\n",
"* if `N=5`: $\\operatorname{elt} = \\operatorname{Adj}_5 + 1.5\\operatorname{Op}_5.$"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:15.015000+02:00",
"start_time": "2019-07-05T20:42:36.842Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"75197-element SparseArrays.SparseVector{Int64,Int64} with 361 stored entries:\n",
" [1 ] = 480\n",
" [2 ] = -40\n",
" [3 ] = -40\n",
" [4 ] = -40\n",
" [5 ] = -40\n",
" [6 ] = -40\n",
" [7 ] = -40\n",
" [8 ] = -40\n",
" [9 ] = -40\n",
" [10 ] = -40\n",
" ⋮\n",
" [418 ] = 1\n",
" [420 ] = 1\n",
" [422 ] = 2\n",
" [423 ] = 1\n",
" [424 ] = 1\n",
" [425 ] = 1\n",
" [426 ] = 1\n",
" [428 ] = 1\n",
" [429 ] = 1\n",
" [430 ] = 1\n",
" [431 ] = 1"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"if N == 3\n",
" k = 0\n",
"elseif N == 4\n",
" k = 1\n",
"elseif N == 5\n",
" k = 1.5\n",
"end\n",
"elt = AdjN + k*OpN;\n",
"elt.coeffs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Optimization Problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We are ready to define the optimisation problem. Function\n",
"> `PropertyT.SOS_problem(x, Δ, orbit_data; upper_bound=UB)` \n",
"\n",
"defines the optimisation problem equivalent to the one of the form\n",
"\\begin{align}\n",
"\\text{ maximize : } \\quad & \\lambda\\\\\n",
"\\text{under constraints : }\\quad & 0 \\leqslant \\lambda \\leqslant \\operatorname{UB},\\\\\n",
" & x - \\lambda \\Delta = \\sum \\xi_i^* \\xi_i,\\\\\n",
" & \\text{each $\\xi_i$ is invariant under $\\mathbb{Z}/2\\mathbb{Z} \\wr \\operatorname{Sym}_N$}.\n",
"\\end{align}"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:23.769000+02:00",
"start_time": "2019-07-05T20:42:36.860Z"
}
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"┌ Info: Adding 558 constraints...\n",
"└ @ PropertyT /home/kalmar/.julia/packages/PropertyT/yHEMH/src/sos_sdps.jl:92\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1.916622 seconds (3.18 M allocations: 408.777 MiB, 12.54% gc time)\n"
]
},
{
"data": {
"text/plain": [
"(A JuMP Model\n",
"Maximization problem with:\n",
"Variables: 1388\n",
"Objective function type: JuMP.VariableRef\n",
"`JuMP.VariableRef`-in-`MathOptInterface.LessThan{Float64}`: 1 constraint\n",
"`JuMP.GenericAffExpr{Float64,JuMP.VariableRef}`-in-`MathOptInterface.EqualTo{Float64}`: 558 constraints\n",
"`Array{JuMP.VariableRef,1}`-in-`MathOptInterface.PositiveSemidefiniteConeSquare`: 14 constraints\n",
"Model mode: AUTOMATIC\n",
"CachingOptimizer state: NO_OPTIMIZER\n",
"Solver name: No optimizer attached.\n",
"Names registered in the model: λ, Array{JuMP.VariableRef,2}[[noname noname noname; noname noname noname; noname noname noname], [noname noname … noname noname; noname noname … noname noname; … ; noname noname … noname noname; noname noname … noname noname], [noname noname … noname noname; noname noname … noname noname; … ; noname noname … noname noname; noname noname … noname noname], [noname noname … noname noname; noname noname … noname noname; … ; noname noname … noname noname; noname noname … noname noname], [noname noname … noname noname; noname noname … noname noname; … ; noname noname … noname noname; noname noname … noname noname], [noname noname … noname noname; noname noname … noname noname; … ; noname noname … noname noname; noname noname … noname noname], [noname noname … noname noname; noname noname … noname noname; … ; noname noname … noname noname; noname noname … noname noname], [noname noname … noname noname; noname noname … noname noname; … ; noname noname … noname noname; noname noname … noname noname], [noname noname … noname noname; noname noname … noname noname; … ; noname noname … noname noname; noname noname … noname noname], [noname], [noname], [noname], [noname noname; noname noname], [noname]])"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# @time SDP_problem, varλ, varP = PropertyT.SOS_problem(elt, Δ, orbit_data)\n",
"if N == 3\n",
" UB = 0.158\n",
"elseif N == 4\n",
" UB = 0.82005\n",
"elseif N == 5\n",
" UB = 1.5005\n",
"end\n",
"SDP_problem, varP = PropertyT.SOS_problem(elt, Δ, orbit_data; upper_bound=UB)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:25.875000+02:00",
"start_time": "2019-07-05T20:42:36.888Z"
}
},
"outputs": [],
"source": [
"using JuMP\n",
"using SCS\n",
"λ = Ps = warm = nothing"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solving the problem\n",
"Depending on the actual problem one may need to tweak the parameters given to the solver:\n",
" * `eps` sets the requested accuracy\n",
" * `max_iters` sets the number of iterations to run before solver gives up\n",
" * `alpha` is a parameter ($\\alpha \\in (0,2)$) which determines the rate of convergence at the cost of the accuracy\n",
" * `acceleration_lookback`: if you experience numerical instability in scs log should be changed to `1` (at the cost of rate of convergence).\n",
" \n",
" The parameters below should be enough to obtain a decent solution for $\\operatorname{SL}(4, \\mathbb{Z}), \\operatorname{SL}(5, \\mathbb{Z})$. \n",
" For $\\operatorname{SL}(3, \\mathbb{Z})$ approximately `1_000_000` of iterations is required; in this case by changing `UB` to $0.15$ (above) a much faster convergence can be observed."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:50.992000+02:00",
"start_time": "2019-07-05T20:42:36.908Z"
},
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"----------------------------------------------------------------------------\n",
"\tSCS v2.0.2 - Splitting Conic Solver\n",
"\t(c) Brendan O'Donoghue, Stanford University, 2012-2017\n",
"----------------------------------------------------------------------------\n",
"Lin-sys: sparse-direct, nnz in A = 130382\n",
"eps = 3.00e-13, alpha = 1.50, max_iters = 10000, normalize = 1, scale = 1.00\n",
"acceleration_lookback = 10, rho_x = 1.00e-03\n",
"Variables n = 1388, constraints m = 1946\n",
"Cones:\tprimal zero / dual free vars: 1196\n",
"\tlinear vars: 1\n",
"\tsd vars: 749, sd blks: 14\n",
"Setup time: 8.46e-02s\n",
"SCS using variable warm-starting\n",
"----------------------------------------------------------------------------\n",
" Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)\n",
"----------------------------------------------------------------------------\n",
" 0| 1.02e+00 1.23e+00 9.75e-01 -3.44e+01 4.76e+00 0.00e+00 2.96e-03 \n",
" 100| 1.68e-04 1.10e-03 1.18e-03 -8.19e-01 -8.16e-01 2.95e-16 1.65e-01 \n",
" 200| 1.86e-04 4.32e-04 1.38e-04 -8.19e-01 -8.20e-01 5.89e-16 3.40e-01 \n",
" 300| 6.04e-05 5.47e-04 1.30e-04 -8.19e-01 -8.19e-01 2.39e-17 5.22e-01 \n",
" 400| 1.35e-04 4.46e-04 2.68e-04 -8.19e-01 -8.20e-01 2.06e-15 6.93e-01 \n",
" 500| 1.35e-04 4.21e-04 3.66e-04 -8.19e-01 -8.20e-01 2.36e-15 8.59e-01 \n",
" 600| 4.90e-05 2.34e-04 2.32e-04 -8.20e-01 -8.19e-01 3.42e-16 1.02e+00 \n",
" 700| 2.12e-05 1.74e-04 1.49e-04 -8.20e-01 -8.19e-01 1.51e-15 1.19e+00 \n",
" 800| 6.12e-05 2.23e-04 2.15e-04 -8.20e-01 -8.19e-01 4.95e-16 1.37e+00 \n",
" 900| 3.99e-05 1.79e-04 3.29e-05 -8.20e-01 -8.20e-01 5.59e-16 1.54e+00 \n",
" 1000| 1.30e-05 1.93e-04 1.04e-04 -8.20e-01 -8.20e-01 1.37e-15 1.72e+00 \n",
" 1100| 2.31e-05 2.01e-04 9.26e-05 -8.20e-01 -8.19e-01 2.58e-16 1.89e+00 \n",
" 1200| 2.15e-05 1.68e-04 2.12e-04 -8.20e-01 -8.19e-01 1.20e-15 2.07e+00 \n",
" 1300| 2.32e-05 1.61e-04 1.64e-04 -8.20e-01 -8.19e-01 5.90e-17 2.24e+00 \n",
" 1400| 1.19e-05 1.13e-04 1.75e-04 -8.20e-01 -8.19e-01 5.17e-16 2.42e+00 \n",
" 1500| 8.01e-06 1.33e-04 8.49e-05 -8.20e-01 -8.20e-01 3.33e-16 2.59e+00 \n",
" 1600| 3.49e-05 1.50e-04 1.04e-04 -8.20e-01 -8.19e-01 3.73e-16 2.76e+00 \n",
" 1700| 2.28e-05 8.89e-05 5.56e-05 -8.20e-01 -8.20e-01 2.86e-16 2.92e+00 \n",
" 1800| 1.54e-05 9.31e-05 1.06e-04 -8.20e-01 -8.20e-01 4.60e-16 3.09e+00 \n",
" 1900| 9.36e-06 1.25e-04 4.95e-06 -8.20e-01 -8.20e-01 3.36e-15 3.26e+00 \n",
" 2000| 3.71e-05 8.99e-05 2.00e-05 -8.20e-01 -8.20e-01 3.53e-16 3.46e+00 \n",
" 2100| 7.38e-06 7.97e-05 5.16e-05 -8.20e-01 -8.20e-01 1.92e-15 3.64e+00 \n",
" 2200| 1.08e-05 7.21e-05 3.00e-05 -8.20e-01 -8.20e-01 8.14e-16 3.81e+00 \n",
" 2300| 6.20e-06 9.69e-05 5.00e-05 -8.20e-01 -8.20e-01 1.36e-15 3.98e+00 \n",
" 2400| 8.47e-06 8.09e-05 6.05e-05 -8.20e-01 -8.20e-01 2.48e-15 4.15e+00 \n",
" 2500| 2.39e-05 8.09e-05 3.22e-05 -8.20e-01 -8.20e-01 3.40e-15 4.33e+00 \n",
" 2600| 1.56e-05 5.56e-05 1.86e-05 -8.20e-01 -8.20e-01 1.13e-16 4.50e+00 \n",
" 2700| 6.45e-06 6.44e-05 7.46e-07 -8.20e-01 -8.20e-01 1.15e-16 4.67e+00 \n",
" 2800| 2.76e-06 4.58e-05 5.44e-05 -8.20e-01 -8.20e-01 3.67e-15 4.84e+00 \n",
" 2900| 3.68e-06 5.38e-05 3.21e-05 -8.20e-01 -8.20e-01 1.04e-15 5.02e+00 \n",
" 3000| 6.13e-06 5.96e-05 5.55e-05 -8.20e-01 -8.20e-01 2.67e-16 5.19e+00 \n",
" 3100| 1.15e-05 4.97e-05 2.32e-06 -8.20e-01 -8.20e-01 4.40e-16 5.37e+00 \n",
" 3200| 1.28e-05 3.79e-05 4.61e-05 -8.20e-01 -8.20e-01 2.80e-15 5.54e+00 \n",
" 3300| 1.01e-05 8.71e-05 3.11e-05 -8.20e-01 -8.20e-01 1.90e-15 5.73e+00 \n",
" 3400| 5.20e-06 4.60e-05 1.14e-05 -8.20e-01 -8.20e-01 1.77e-16 5.90e+00 \n",
" 3500| 2.60e-06 2.80e-05 1.28e-05 -8.20e-01 -8.20e-01 7.29e-16 6.06e+00 \n",
" 3600| 6.14e-06 4.07e-05 1.17e-05 -8.20e-01 -8.20e-01 1.41e-15 6.23e+00 \n",
" 3700| 2.59e-06 2.02e-05 7.04e-06 -8.20e-01 -8.20e-01 7.81e-16 6.40e+00 \n",
" 3800| 5.14e-06 3.43e-05 2.91e-05 -8.20e-01 -8.20e-01 3.08e-16 6.59e+00 \n",
" 3900| 1.77e-06 2.43e-05 3.56e-07 -8.20e-01 -8.20e-01 1.42e-15 6.75e+00 \n",
" 4000| 6.59e-06 2.22e-05 1.03e-05 -8.20e-01 -8.20e-01 2.65e-16 6.92e+00 \n",
" 4100| 2.81e-06 2.11e-05 1.35e-05 -8.20e-01 -8.20e-01 1.65e-15 7.09e+00 \n",
" 4200| 1.90e-06 2.91e-05 2.26e-05 -8.20e-01 -8.20e-01 1.54e-15 7.26e+00 \n",
" 4300| 4.63e-06 3.09e-05 1.42e-06 -8.20e-01 -8.20e-01 1.15e-15 7.43e+00 \n",
" 4400| 2.02e-06 1.69e-05 7.11e-06 -8.20e-01 -8.20e-01 8.27e-16 7.61e+00 \n",
" 4500| 9.67e-06 2.00e-05 5.91e-06 -8.20e-01 -8.20e-01 5.69e-16 7.77e+00 \n",
" 4600| 8.40e-07 4.23e-06 3.47e-06 -8.20e-01 -8.20e-01 2.54e-15 7.93e+00 \n",
" 4700| 1.33e-06 9.78e-06 4.42e-08 -8.20e-01 -8.20e-01 8.54e-16 8.09e+00 \n",
" 4800| 8.40e-07 2.94e-06 4.89e-06 -8.20e-01 -8.20e-01 2.71e-15 8.25e+00 \n",
" 4900| 5.06e-07 1.84e-06 1.09e-06 -8.20e-01 -8.20e-01 2.43e-15 8.40e+00 \n",
" 5000| 1.26e-06 3.09e-06 4.54e-06 -8.20e-01 -8.20e-01 5.48e-17 8.55e+00 \n",
" 5100| 1.15e-07 2.30e-07 2.20e-07 -8.20e-01 -8.20e-01 4.83e-15 8.71e+00 \n",
" 5200| 2.57e-08 2.21e-07 2.86e-09 -8.20e-01 -8.20e-01 3.43e-15 8.85e+00 \n",
" 5300| 1.07e-04 2.94e-04 2.86e-04 -8.20e-01 -8.21e-01 4.81e-12 9.00e+00 \n",
" 5400| 8.39e-09 1.30e-07 8.58e-08 -8.20e-01 -8.20e-01 1.72e-15 9.14e+00 \n",
" 5500| 1.12e-08 1.68e-07 9.26e-09 -8.20e-01 -8.20e-01 2.03e-15 9.30e+00 \n",
" 5600| 2.88e-06 1.85e-05 1.04e-05 -8.20e-01 -8.20e-01 6.67e-15 9.45e+00 \n",
" 5700| 2.10e-05 2.21e-04 7.80e-05 -8.20e-01 -8.20e-01 8.08e-15 9.65e+00 \n",
" 5800| 4.36e-07 1.32e-06 8.45e-07 -8.20e-01 -8.20e-01 1.36e-15 9.80e+00 \n",
" 5900| 3.68e-06 3.39e-05 1.88e-06 -8.20e-01 -8.20e-01 1.39e-15 9.95e+00 \n",
" 6000| 2.28e-08 2.05e-07 9.89e-08 -8.20e-01 -8.20e-01 1.26e-15 1.01e+01 \n",
" 6100| 4.73e-08 7.77e-08 3.29e-08 -8.20e-01 -8.20e-01 1.86e-15 1.03e+01 \n",
" 6200| 5.33e-09 1.65e-08 1.07e-08 -8.20e-01 -8.20e-01 2.61e-16 1.04e+01 \n",
" 6300| 5.08e-08 3.23e-07 2.44e-07 -8.20e-01 -8.20e-01 1.71e-14 1.05e+01 \n",
" 6400| 5.01e-14 8.48e-13 4.12e-13 -8.20e-01 -8.20e-01 4.17e-16 1.07e+01 \n",
" 6402| 4.42e-14 1.73e-13 6.97e-14 -8.20e-01 -8.20e-01 7.23e-16 1.07e+01 \n",
"----------------------------------------------------------------------------\n",
"Status: Solved\n",
"Timing: Solve time: 1.07e+01s\n",
"\tLin-sys: nnz in L factor: 288182, avg solve time: 1.00e-03s\n",
"\tCones: avg projection time: 4.08e-04s\n",
"\tAcceleration: avg step time: 1.74e-04s\n",
"----------------------------------------------------------------------------\n",
"Error metrics:\n",
"dist(s, K) = 8.4711e-10, dist(y, K*) = 2.4476e-09, s'y/|s||y| = -3.2607e-15\n",
"primal res: |Ax + s - b|_2 / (1 + |b|_2) = 4.4176e-14\n",
"dual res: |A'y + c|_2 / (1 + |c|_2) = 1.7338e-13\n",
"rel gap: |c'x + b'y| / (1 + |c'x| + |b'y|) = 6.9723e-14\n",
"----------------------------------------------------------------------------\n",
"c'x = -0.8201, -b'y = -0.8201\n",
"============================================================================\n"
]
}
],
"source": [
"with_SCS = with_optimizer(SCS.Optimizer, \n",
" linear_solver=SCS.Direct, \n",
" eps=3e-13,\n",
" max_iters=10000,\n",
" alpha=1.5,\n",
" acceleration_lookback=10,\n",
" warm_start=true)\n",
"\n",
"status, warm = PropertyT.solve(SDP_problem, with_SCS, warm);"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:51.426000+02:00",
"start_time": "2019-07-05T20:42:36.925Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"status = OPTIMAL::TerminationStatusCode = 1\n",
"λ = 0.8200500000003405\n"
]
}
],
"source": [
"λ = value(SDP_problem[:λ])\n",
"Ps = [value.(P) for P in varP]\n",
"@show(status, λ);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Checking the solution\n",
"Now we reconstruct the solution to the original problem over $\\mathbb{R} \\operatorname{SL}(N,\\mathbb{Z})$, which essentially boils down to averaging the obtained solution over the orbits of wreath product action:\n",
" $$Q=\\frac{1}{|\\Sigma|}\\sum_{\\sigma\\in\\Sigma}\\sum_{\\pi\\in \\widehat{\\Sigma}} \\dim{\\pi}\\cdot\\sigma\\left(U_{\\pi}^T \\sqrt{P_{\\pi}} U_{\\pi}\\right).$$"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:57.528000+02:00",
"start_time": "2019-07-05T20:42:36.935Z"
}
},
"outputs": [],
"source": [
"Qs = real.(sqrt.(Ps));\n",
"Q = PropertyT.reconstruct(Qs, orbit_data);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As explained in the paper the columns of the square-root of the solution matrix provide the coefficients for $\\xi_i$'s in basis `E_R` of the group ring. Below we compute the residual \n",
" $$ b = \\left(x - \\lambda\\Delta\\right) - \\sum \\xi_i^*\\xi_i.$$\n",
"As we do it in floating-point arithmetic, the result can't be taken seriously."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:58.109000+02:00",
"start_time": "2019-07-05T20:42:36.951Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"SOS_residual (generic function with 1 method)"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"function SOS_residual(x::GroupRingElem, Q::Matrix)\n",
" RG = parent(x)\n",
" @time sos = PropertyT.compute_SOS(RG, Q);\n",
" return x - sos\n",
"end"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:59.032000+02:00",
"start_time": "2019-07-05T20:42:36.961Z"
}
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"┌ Warning: Scalar and coeffs are in different rings! Promoting result to Float64\n",
"└ @ GroupRings /home/kalmar/.julia/packages/GroupRings/UwACc/src/GroupRings.jl:303\n",
"┌ Warning: Adding elements with different coefficient rings, Promoting result to Float64\n",
"└ @ GroupRings /home/kalmar/.julia/packages/GroupRings/UwACc/src/GroupRings.jl:341\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 0.017873 seconds (977 allocations: 2.065 MiB)\n",
"norm(residual, 1) = 8.53743030863061e-9\n"
]
}
],
"source": [
"residual = SOS_residual(elt - λ*Δ, Q)\n",
"@show norm(residual, 1);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Checking in interval arithmetic"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:43:59.290000+02:00",
"start_time": "2019-07-05T20:42:36.979Z"
}
},
"outputs": [],
"source": [
"using IntervalArithmetic\n",
"IntervalArithmetic.setrounding(Interval, :tight)\n",
"IntervalArithmetic.setformat(sigfigs=12);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here we resort to interval arithmetic to provide certified upper and lower bounds on the norm of the residual.\n",
"* We first change entries of `Q` to narrow intervals\n",
"* We project columns of `Q` so that $0$ is in the sum of coefficients of each column (i.e. $\\xi_i \\in I \\operatorname{SL}(N,\\mathbb{Z})$)\n",
"* We compute the sum of squares and the $\\ell_1$-norm of the residual in the interval arithmetic.\n",
"\n",
"The returned `check_columns_augmentation` is a boolean flag to detect if the projection was successful, i.e. if we can guarantee that each column of `Q_aug` can be represented by an element from the augmentation ideal. (If it were not successful, one may project `Q = PropertyT.augIdproj(Q)` in the floating point arithmetic prior to the cell below).\n",
"\n",
"The resulting norm of the residual is **guaranteed** to be contained in the resulting interval. E.g. if each entry of `Q` were changed into an honest rational number and all the computations were carried out in rational arithmetic, the rational $\\ell_1$-norm will be contained in the interval $\\ell_1$-norm."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:44:08.135000+02:00",
"start_time": "2019-07-05T20:42:36.999Z"
}
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"┌ Warning: Scalar and coeffs are in different rings! Promoting result to Interval{Float64}\n",
"└ @ GroupRings /home/kalmar/.julia/packages/GroupRings/UwACc/src/GroupRings.jl:303\n",
"┌ Warning: Adding elements with different coefficient rings, Promoting result to Interval{Float64}\n",
"└ @ GroupRings /home/kalmar/.julia/packages/GroupRings/UwACc/src/GroupRings.jl:341\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 3.296487 seconds (976 allocations: 4.070 MiB)\n",
"norm(residual_int, 1) = [1.06387679475e-08, 1.09608901207e-08]\n"
]
}
],
"source": [
"Q_aug, check_columns_augmentation = PropertyT.augIdproj(Interval, Q);\n",
"@assert check_columns_augmentation\n",
"elt_int = elt - @interval(λ)*Δ;\n",
"residual_int = SOS_residual(elt_int, Q_aug)\n",
"@show norm(residual_int, 1);"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:44:09.222000+02:00",
"start_time": "2019-07-05T20:42:37.015Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"[0.820049956156, 0.820049957446]"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"certified_λ = @interval(λ) - 2^2*norm(residual_int,1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"ExecuteTime": {
"end_time": "2018-11-24T14:06:31.828000+01:00",
"start_time": "2018-11-24T13:06:31.206Z"
}
},
"source": [
"So $\\operatorname{elt} - \\lambda_0 \\Delta \\in \\Sigma^2 I\\operatorname{SL}(N, \\mathbb{Z})$, where as $\\lambda_0$ we could take the left end of the above interval:"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:44:09.948000+02:00",
"start_time": "2019-07-05T20:42:37.032Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"0.8200499561567799"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"certified_λ.lo"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:44:10.008000+02:00",
"start_time": "2019-07-05T20:42:37.045Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"2019-07-05T22:44:09.949"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"using Dates\n",
"now()"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-05T22:44:12.077000+02:00",
"start_time": "2019-07-05T20:42:37.052Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Julia Version 1.1.1\n",
"Commit 55e36cc308 (2019-05-16 04:10 UTC)\n",
"Platform Info:\n",
" OS: Linux (x86_64-pc-linux-gnu)\n",
" CPU: Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz\n",
" WORD_SIZE: 64\n",
" LIBM: libopenlibm\n",
" LLVM: libLLVM-6.0.1 (ORCJIT, skylake)\n",
"Environment:\n",
" JULIA_NUM_THREADS = 2\n"
]
}
],
"source": [
"versioninfo()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"@webio": {
"lastCommId": null,
"lastKernelId": null
},
"gist": {
"data": {
"description": "ownCloud/GroupsWithPropertyT/notebooks/Positivity in SL(n,Z).ipynb",
"public": false
},
"id": ""
},
"kernelspec": {
"display_name": "Julia 1.1.1",
"language": "julia",
"name": "julia-1.1"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.1.1"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": false,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment