simplified "sos" method;
authorwenzelm
Wed Oct 08 11:09:17 2014 +0200 (2014-10-08)
changeset 5863071cdb885b3bb
parent 58629 a6a6cd499d4e
child 58631 41333b45bff9
simplified "sos" method;
NEWS
src/HOL/Library/Sum_of_Squares.thy
src/HOL/Library/Sum_of_Squares/etc/settings
src/HOL/Library/Sum_of_Squares/neos_csdp_client
src/HOL/Library/Sum_of_Squares/sos_wrapper.ML
src/HOL/ROOT
src/HOL/ex/SOS.thy
src/HOL/ex/SOS_Cert.thy
src/HOL/ex/SOS_Remote.thy
     1.1 --- a/NEWS	Wed Oct 08 10:15:04 2014 +0200
     1.2 +++ b/NEWS	Wed Oct 08 11:09:17 2014 +0200
     1.3 @@ -126,6 +126,12 @@
     1.4    generated code in target languages in HOL/Library/Code_Test. See
     1.5    HOL/Codegenerator_Test/Code_Test* for examples.
     1.6  
     1.7 +* Library/Sum_of_Squares: simplified and improved "sos" method. Always
     1.8 +use local CSDP executable, which is much faster than the NEOS server.
     1.9 +The "sos_cert" functionality is invoked as "sos" with additional
    1.10 +argument. Minor INCOMPATIBILITY.
    1.11 +
    1.12 +
    1.13  *** ML ***
    1.14  
    1.15  * Tactical PARALLEL_ALLGOALS is the most common way to refer to
     2.1 --- a/src/HOL/Library/Sum_of_Squares.thy	Wed Oct 08 10:15:04 2014 +0200
     2.2 +++ b/src/HOL/Library/Sum_of_Squares.thy	Wed Oct 08 11:09:17 2014 +0200
     2.3 @@ -3,8 +3,8 @@
     2.4      Author:     Philipp Meyer, TU Muenchen
     2.5  *)
     2.6  
     2.7 -header {* A decision method for universal multivariate real arithmetic with addition, 
     2.8 -  multiplication and ordering using semidefinite programming *}
     2.9 +header {* A decision procedure for universal multivariate real arithmetic
    2.10 +  with addition, multiplication and ordering using semidefinite programming *}
    2.11  
    2.12  theory Sum_of_Squares
    2.13  imports Complex_Main
    2.14 @@ -15,27 +15,4 @@
    2.15  ML_file "Sum_of_Squares/positivstellensatz_tools.ML"
    2.16  ML_file "Sum_of_Squares/sos_wrapper.ML"
    2.17  
    2.18 -text {*
    2.19 -  Proof method sos invocations:
    2.20 -  \begin{itemize}
    2.21 -
    2.22 -  \item remote solver: @{text "(sos remote_csdp)"}
    2.23 -
    2.24 -  \item local solver: @{text "(sos csdp)"}
    2.25 -
    2.26 -  The latter requires a local executable from
    2.27 -  @{url "https://projects.coin-or.org/Csdp"} and the Isabelle settings variable
    2.28 -  variable @{text ISABELLE_CSDP} pointing to it.
    2.29 -
    2.30 -  \end{itemize}
    2.31 -
    2.32 -  By default, method sos calls @{text remote_csdp}.  This can take of
    2.33 -  the order of a minute for one sos call, because sos calls CSDP
    2.34 -  repeatedly.  If you install CSDP locally, sos calls typically takes
    2.35 -  only a few seconds.
    2.36 -
    2.37 -  The sos method generates a certificate which can be used to repeat
    2.38 -  the proof without calling an external prover.
    2.39 -*}
    2.40 -
    2.41  end
     3.1 --- a/src/HOL/Library/Sum_of_Squares/etc/settings	Wed Oct 08 10:15:04 2014 +0200
     3.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.3 @@ -1,8 +0,0 @@
     3.4 -# -*- shell-script -*- :mode=shellscript:
     3.5 -
     3.6 -ISABELLE_SUM_OF_SQUARES="$COMPONENT"
     3.7 -ISABELLE_NEOS_SERVER="http://neos-server.org:3332"
     3.8 -
     3.9 -# local SDP Solver, cf. https://projects.coin-or.org/Csdp
    3.10 -#ISABELLE_CSDP="/usr/local/bin/csdp"
    3.11 -
     4.1 --- a/src/HOL/Library/Sum_of_Squares/neos_csdp_client	Wed Oct 08 10:15:04 2014 +0200
     4.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.3 @@ -1,85 +0,0 @@
     4.4 -#!/usr/bin/env python
     4.5 -import sys
     4.6 -import signal
     4.7 -import xmlrpclib
     4.8 -import time
     4.9 -import re
    4.10 -import os
    4.11 -
    4.12 -# Neos server config
    4.13 -neos = xmlrpclib.Server(os.getenv("ISABELLE_NEOS_SERVER"))
    4.14 -
    4.15 -jobNumber = 0
    4.16 -password = ""
    4.17 -inputfile = None
    4.18 -outputfile = None
    4.19 -# interrupt handler
    4.20 -def cleanup(signal, frame):
    4.21 -  sys.stdout.write("Caught interrupt, cleaning up\n")
    4.22 -  if jobNumber != 0:
    4.23 -    neos.killJob(jobNumber, password)
    4.24 -  if inputfile != None:
    4.25 -    inputfile.close()
    4.26 -  if outputfile != None:
    4.27 -    outputfile.close()
    4.28 -  sys.exit(21)
    4.29 -
    4.30 -signal.signal(signal.SIGHUP, cleanup)
    4.31 -signal.signal(signal.SIGINT, cleanup)
    4.32 -signal.signal(signal.SIGQUIT, cleanup)
    4.33 -signal.signal(signal.SIGTERM, cleanup)
    4.34 -
    4.35 -if len(sys.argv) <> 3:
    4.36 -  sys.stderr.write("Usage: neos_csdp_client <input_filename> <output_filename>\n")
    4.37 -  sys.exit(19)
    4.38 -
    4.39 -xml_pre = "<document>\n<category>sdp</category>\n<solver>csdp</solver>\n<inputMethod>SPARSE_SDPA</inputMethod>\n<dat><![CDATA["
    4.40 -xml_post = "]]></dat>\n</document>\n"
    4.41 -xml = xml_pre
    4.42 -inputfile = open(sys.argv[1],"r")
    4.43 -buffer = 1
    4.44 -while buffer:
    4.45 -  buffer = inputfile.read()
    4.46 -  xml += buffer
    4.47 -inputfile.close()
    4.48 -xml += xml_post
    4.49 -
    4.50 -(jobNumber,password) = neos.submitJob(xml)
    4.51 -
    4.52 -if jobNumber == 0:
    4.53 -  sys.stdout.write("error submitting job: %s" % password)
    4.54 -  sys.exit(20)
    4.55 -else:
    4.56 -  sys.stdout.write("jobNumber = %d\tpassword = %s\n" % (jobNumber,password))
    4.57 -
    4.58 -offset=0
    4.59 -messages = ""
    4.60 -status="Waiting"
    4.61 -while status == "Running" or status=="Waiting":
    4.62 -  time.sleep(1)
    4.63 -  (msg,offset) = neos.getIntermediateResults(jobNumber,password,offset)
    4.64 -  messages += msg.data
    4.65 -  sys.stdout.write(msg.data)
    4.66 -  status = neos.getJobStatus(jobNumber, password)
    4.67 -
    4.68 -msg = neos.getFinalResults(jobNumber, password).data
    4.69 -sys.stdout.write("---------- Begin CSDP Output -------------\n");
    4.70 -sys.stdout.write(msg)
    4.71 -
    4.72 -# extract solution
    4.73 -result = msg.split("Solution:")
    4.74 -if len(result) > 1:
    4.75 -  solution = result[1].strip()
    4.76 -  if solution != "":
    4.77 -    outputfile = open(sys.argv[2],"w")
    4.78 -    outputfile.write(solution)
    4.79 -    outputfile.close()
    4.80 -
    4.81 -# extract return code
    4.82 -p = re.compile(r"^Error: Command exited with non-zero status (\d+)$", re.MULTILINE)
    4.83 -m = p.search(messages)
    4.84 -if m:
    4.85 -  sys.exit(int(m.group(1)))
    4.86 -else:
    4.87 -  sys.exit(0)
    4.88 -
     5.1 --- a/src/HOL/Library/Sum_of_Squares/sos_wrapper.ML	Wed Oct 08 10:15:04 2014 +0200
     5.2 +++ b/src/HOL/Library/Sum_of_Squares/sos_wrapper.ML	Wed Oct 08 11:09:17 2014 +0200
     5.3 @@ -6,9 +6,7 @@
     5.4  
     5.5  signature SOS_WRAPPER =
     5.6  sig
     5.7 -  datatype prover_result = Success | Failure | Error
     5.8 -  val dest_dir: string Config.T
     5.9 -  val prover_name: string Config.T
    5.10 +  val sos_tac: Proof.context -> string option -> int -> tactic
    5.11  end
    5.12  
    5.13  structure SOS_Wrapper: SOS_WRAPPER =
    5.14 @@ -21,33 +19,33 @@
    5.15    | str_of_result Error = "Error"
    5.16  
    5.17  
    5.18 -(*** calling provers ***)
    5.19 +fun filename name =
    5.20 +  File.tmp_path (Path.basic (name ^ serial_string ()))
    5.21  
    5.22 -val dest_dir = Attrib.setup_config_string @{binding sos_dest_dir} (K "")
    5.23 +fun find_failure rv =
    5.24 +  case rv of
    5.25 +    0 => (Success, "SDP solved")
    5.26 +  | 1 => (Failure, "SDP is primal infeasible")
    5.27 +  | 2 => (Failure, "SDP is dual infeasible")
    5.28 +  | 3 => (Success, "SDP solved with reduced accuracy")
    5.29 +  | 4 => (Failure, "Maximum iterations reached")
    5.30 +  | 5 => (Failure, "Stuck at edge of primal feasibility")
    5.31 +  | 6 => (Failure, "Stuck at edge of dual infeasibility")
    5.32 +  | 7 => (Failure, "Lack of progress")
    5.33 +  | 8 => (Failure, "X, Z, or O was singular")
    5.34 +  | 9 => (Failure, "Detected NaN or Inf values")
    5.35 +  | _ => (Error, "return code is " ^ string_of_int rv)
    5.36  
    5.37 -fun filename dir name =
    5.38 +val exe = Path.explode "$ISABELLE_CSDP"
    5.39 +
    5.40 +fun run_solver ctxt input =
    5.41    let
    5.42 -    val probfile = Path.basic (name ^ serial_string ())
    5.43 -    val dir_path = Path.explode dir
    5.44 -  in
    5.45 -    if dir = "" then
    5.46 -      File.tmp_path probfile
    5.47 -    else if File.exists dir_path then
    5.48 -      Path.append dir_path probfile
    5.49 -    else error ("No such directory: " ^ dir)
    5.50 -  end
    5.51 -
    5.52 -fun run_solver ctxt name exe find_failure input =
    5.53 -  let
    5.54 -    val _ = warning ("Calling solver: " ^ name)
    5.55 -
    5.56      (* create input file *)
    5.57 -    val dir = Config.get ctxt dest_dir
    5.58 -    val input_file = filename dir "sos_in"
    5.59 +    val input_file = filename "sos_in"
    5.60      val _ = File.write input_file input
    5.61  
    5.62      (* call solver *)
    5.63 -    val output_file = filename dir "sos_out"
    5.64 +    val output_file = filename "sos_out"
    5.65      val (output, rv) =
    5.66        Isabelle_System.bash_output
    5.67         (if File.exists exe then
    5.68 @@ -59,10 +57,8 @@
    5.69      val result = if File.exists output_file then File.read output_file else ""
    5.70  
    5.71      (* remove temporary files *)
    5.72 -    val _ =
    5.73 -      if dir = "" then
    5.74 -        (File.rm input_file; if File.exists output_file then File.rm output_file else ())
    5.75 -      else ()
    5.76 +    val _ = File.rm input_file
    5.77 +    val _ = if File.exists output_file then File.rm output_file else ()
    5.78  
    5.79      val _ =
    5.80        if Config.get ctxt Sum_of_Squares.trace
    5.81 @@ -78,78 +74,24 @@
    5.82    end
    5.83  
    5.84  
    5.85 -(*** various provers ***)
    5.86 -
    5.87 -(* local csdp client *)
    5.88 -
    5.89 -fun find_csdp_failure rv =
    5.90 -  case rv of
    5.91 -    0 => (Success, "SDP solved")
    5.92 -  | 1 => (Failure, "SDP is primal infeasible")
    5.93 -  | 2 => (Failure, "SDP is dual infeasible")
    5.94 -  | 3 => (Success, "SDP solved with reduced accuracy")
    5.95 -  | 4 => (Failure, "Maximum iterations reached")
    5.96 -  | 5 => (Failure, "Stuck at edge of primal feasibility")
    5.97 -  | 6 => (Failure, "Stuck at edge of dual infeasibility")
    5.98 -  | 7 => (Failure, "Lack of progress")
    5.99 -  | 8 => (Failure, "X, Z, or O was singular")
   5.100 -  | 9 => (Failure, "Detected NaN or Inf values")
   5.101 -  | _ => (Error, "return code is " ^ string_of_int rv)
   5.102 -
   5.103 -val csdp = (Path.explode "$ISABELLE_CSDP", find_csdp_failure)
   5.104 -
   5.105 -
   5.106 -(* remote neos server *)
   5.107 -
   5.108 -fun find_neos_failure rv =
   5.109 -  case rv of
   5.110 -    20 => (Error, "error submitting job")
   5.111 -  | 21 => (Error, "interrupt")
   5.112 -  |  _ => find_csdp_failure rv
   5.113 -
   5.114 -val neos_csdp = (Path.explode "$ISABELLE_SUM_OF_SQUARES/neos_csdp_client", find_neos_failure)
   5.115 -
   5.116 -
   5.117 -(* named provers *)
   5.118 -
   5.119 -fun prover "remote_csdp" = neos_csdp
   5.120 -  | prover "csdp" = csdp
   5.121 -  | prover name = error ("Unknown prover: " ^ name)
   5.122 -
   5.123 -val prover_name = Attrib.setup_config_string @{binding sos_prover_name} (K "remote_csdp")
   5.124 -
   5.125 -fun call_solver ctxt opt_name =
   5.126 -  let
   5.127 -    val name = the_default (Config.get ctxt prover_name) opt_name
   5.128 -    val (exe, find_failure) = prover name
   5.129 -  in run_solver ctxt name exe find_failure end
   5.130 -
   5.131 -
   5.132 -(* certificate output *)
   5.133 -
   5.134 -fun output_line cert =
   5.135 -  "To repeat this proof with a certificate use this command:\n" ^
   5.136 -    Active.sendback_markup [] ("apply (sos_cert \"" ^ cert ^ "\")")
   5.137 -
   5.138 -val print_cert = warning o output_line o Positivstellensatz_Tools.print_cert
   5.139 -
   5.140 -
   5.141  (* method setup *)
   5.142  
   5.143 -fun sos_solver print method = SIMPLE_METHOD' o Sum_of_Squares.sos_tac print method
   5.144 +fun print_cert cert =
   5.145 +  warning
   5.146 +    ("To repeat this proof with a certificate use this proof method:\n" ^
   5.147 +      Active.sendback_markup [] ("(sos \"" ^ Positivstellensatz_Tools.print_cert cert ^ "\")"))
   5.148 +
   5.149 +fun sos_tac ctxt NONE =
   5.150 +      Sum_of_Squares.sos_tac print_cert
   5.151 +        (Sum_of_Squares.Prover (run_solver ctxt)) ctxt
   5.152 +  | sos_tac ctxt (SOME cert) =
   5.153 +      Sum_of_Squares.sos_tac ignore
   5.154 +        (Sum_of_Squares.Certificate (Positivstellensatz_Tools.read_cert ctxt cert)) ctxt
   5.155  
   5.156  val _ = Theory.setup
   5.157   (Method.setup @{binding sos}
   5.158 -    (Scan.lift (Scan.option Parse.xname)
   5.159 -      >> (fn opt_name => fn ctxt =>
   5.160 -        sos_solver print_cert
   5.161 -          (Sum_of_Squares.Prover (call_solver ctxt opt_name)) ctxt))
   5.162 -    "prove universal problems over the reals using sums of squares" #>
   5.163 -  Method.setup @{binding sos_cert}
   5.164 -    (Scan.lift Parse.string
   5.165 -      >> (fn cert => fn ctxt =>
   5.166 -        sos_solver ignore
   5.167 -          (Sum_of_Squares.Certificate (Positivstellensatz_Tools.read_cert ctxt cert)) ctxt))
   5.168 -    "prove universal problems over the reals using sums of squares with certificates")
   5.169 +    (Scan.lift (Scan.option Parse.string)
   5.170 +      >> (fn arg => fn ctxt => SIMPLE_METHOD' (sos_tac ctxt arg)))
   5.171 +    "prove universal problems over the reals using sums of squares")
   5.172  
   5.173  end
     6.1 --- a/src/HOL/ROOT	Wed Oct 08 10:15:04 2014 +0200
     6.2 +++ b/src/HOL/ROOT	Wed Oct 08 11:09:17 2014 +0200
     6.3 @@ -600,11 +600,8 @@
     6.4      ML
     6.5      SAT_Examples
     6.6      Nominal2_Dummy
     6.7 +    SOS
     6.8      SOS_Cert
     6.9 -  theories [condition = ISABELLE_CSDP]
    6.10 -    SOS
    6.11 -  theories [condition = ISABELLE_FULL_TEST]
    6.12 -    SOS_Remote
    6.13    theories [skip_proofs = false]
    6.14      Meson_Test
    6.15    theories [condition = SVC_HOME]
     7.1 --- a/src/HOL/ex/SOS.thy	Wed Oct 08 10:15:04 2014 +0200
     7.2 +++ b/src/HOL/ex/SOS.thy	Wed Oct 08 11:09:17 2014 +0200
     7.3 @@ -10,121 +10,121 @@
     7.4  begin
     7.5  
     7.6  lemma "(3::real) * x + 7 * a < 4 & 3 < 2 * x \<Longrightarrow> a < 0"
     7.7 -  by (sos csdp)
     7.8 +  by sos
     7.9  
    7.10  lemma "a1 >= 0 & a2 >= 0 \<and> (a1 * a1 + a2 * a2 = b1 * b1 + b2 * b2 + 2) \<and> (a1 * b1 + a2 * b2 = 0) --> a1 * a2 - b1 * b2 >= (0::real)"
    7.11 -  by (sos csdp)
    7.12 +  by sos
    7.13  
    7.14  lemma "(3::real) * x + 7 * a < 4 & 3 < 2 * x --> a < 0"
    7.15 -  by (sos csdp)
    7.16 +  by sos
    7.17  
    7.18  lemma "(0::real) <= x & x <= 1 & 0 <= y & y <= 1  --> x^2 + y^2 < 1 |(x - 1)^2 + y^2 < 1 | x^2 + (y - 1)^2 < 1 | (x - 1)^2 + (y - 1)^2 < 1"
    7.19 -  by (sos csdp)
    7.20 +  by sos
    7.21  
    7.22  lemma "(0::real) <= x & 0 <= y & 0 <= z & x + y + z <= 3 --> x * y + x * z + y * z >= 3 * x * y * z"
    7.23 -  by (sos csdp)
    7.24 +  by sos
    7.25  
    7.26  lemma "((x::real)^2 + y^2 + z^2 = 1) --> (x + y + z)^2 <= 3"
    7.27 -  by (sos csdp)
    7.28 +  by sos
    7.29  
    7.30  lemma "(w^2 + x^2 + y^2 + z^2 = 1) --> (w + x + y + z)^2 <= (4::real)"
    7.31 -  by (sos csdp)
    7.32 +  by sos
    7.33  
    7.34  lemma "(x::real) >= 1 & y >= 1 --> x * y >= x + y - 1"
    7.35 -  by (sos csdp)
    7.36 +  by sos
    7.37  
    7.38  lemma "(x::real) > 1 & y > 1 --> x * y > x + y - 1"
    7.39 -  by (sos csdp)
    7.40 +  by sos
    7.41  
    7.42  lemma "abs(x) <= 1 --> abs(64 * x^7 - 112 * x^5 + 56 * x^3 - 7 * x) <= (1::real)"
    7.43 -  by (sos csdp)
    7.44 +  by sos
    7.45  
    7.46  
    7.47  text \<open>One component of denominator in dodecahedral example.\<close>
    7.48  
    7.49  lemma "2 <= x & x <= 125841 / 50000 & 2 <= y & y <= 125841 / 50000 & 2 <= z & z <= 125841 / 50000 --> 2 * (x * z + x * y + y * z) - (x * x + y * y + z * z) >= (0::real)"
    7.50 -  by (sos csdp)
    7.51 +  by sos
    7.52  
    7.53  
    7.54  text \<open>Over a larger but simpler interval.\<close>
    7.55  
    7.56  lemma "(2::real) <= x & x <= 4 & 2 <= y & y <= 4 & 2 <= z & z <= 4 --> 0 <= 2 * (x * z + x * y + y * z) - (x * x + y * y + z * z)"
    7.57 -  by (sos csdp)
    7.58 +  by sos
    7.59  
    7.60  
    7.61  text \<open>We can do 12. I think 12 is a sharp bound; see PP's certificate.\<close>
    7.62  
    7.63  lemma "2 <= (x::real) & x <= 4 & 2 <= y & y <= 4 & 2 <= z & z <= 4 --> 12 <= 2 * (x * z + x * y + y * z) - (x * x + y * y + z * z)"
    7.64 -  by (sos csdp)
    7.65 +  by sos
    7.66  
    7.67  
    7.68  text \<open>Inequality from sci.math (see "Leon-Sotelo, por favor").\<close>
    7.69  
    7.70  lemma "0 <= (x::real) & 0 <= y & (x * y = 1) --> x + y <= x^2 + y^2"
    7.71 -  by (sos csdp)
    7.72 +  by sos
    7.73  
    7.74  lemma "0 <= (x::real) & 0 <= y & (x * y = 1) --> x * y * (x + y) <= x^2 + y^2"
    7.75 -  by (sos csdp)
    7.76 +  by sos
    7.77  
    7.78  lemma "0 <= (x::real) & 0 <= y --> x * y * (x + y)^2 <= (x^2 + y^2)^2"
    7.79 -  by (sos csdp)
    7.80 +  by sos
    7.81  
    7.82  lemma "(0::real) <= a & 0 <= b & 0 <= c & c * (2 * a + b)^3/ 27 <= x \<longrightarrow> c * a^2 * b <= x"
    7.83 -  by (sos csdp)
    7.84 +  by sos
    7.85  
    7.86  lemma "(0::real) < x --> 0 < 1 + x + x^2"
    7.87 -  by (sos csdp)
    7.88 +  by sos
    7.89  
    7.90  lemma "(0::real) <= x --> 0 < 1 + x + x^2"
    7.91 -  by (sos csdp)
    7.92 +  by sos
    7.93  
    7.94  lemma "(0::real) < 1 + x^2"
    7.95 -  by (sos csdp)
    7.96 +  by sos
    7.97  
    7.98  lemma "(0::real) <= 1 + 2 * x + x^2"
    7.99 -  by (sos csdp)
   7.100 +  by sos
   7.101  
   7.102  lemma "(0::real) < 1 + abs x"
   7.103 -  by (sos csdp)
   7.104 +  by sos
   7.105  
   7.106  lemma "(0::real) < 1 + (1 + x)^2 * (abs x)"
   7.107 -  by (sos csdp)
   7.108 +  by sos
   7.109  
   7.110  
   7.111  lemma "abs ((1::real) + x^2) = (1::real) + x^2"
   7.112 -  by (sos csdp)
   7.113 +  by sos
   7.114  lemma "(3::real) * x + 7 * a < 4 \<and> 3 < 2 * x \<longrightarrow> a < 0"
   7.115 -  by (sos csdp)
   7.116 +  by sos
   7.117  
   7.118  lemma "(0::real) < x --> 1 < y --> y * x <= z --> x < z"
   7.119 -  by (sos csdp)
   7.120 +  by sos
   7.121  lemma "(1::real) < x --> x^2 < y --> 1 < y"
   7.122 -  by (sos csdp)
   7.123 +  by sos
   7.124  lemma "(b::real)^2 < 4 * a * c --> ~(a * x^2 + b * x + c = 0)"
   7.125 -  by (sos csdp)
   7.126 +  by sos
   7.127  lemma "(b::real)^2 < 4 * a * c --> ~(a * x^2 + b * x + c = 0)"
   7.128 -  by (sos csdp)
   7.129 +  by sos
   7.130  lemma "((a::real) * x^2 + b * x + c = 0) --> b^2 >= 4 * a * c"
   7.131 -  by (sos csdp)
   7.132 +  by sos
   7.133  lemma "(0::real) <= b & 0 <= c & 0 <= x & 0 <= y & (x^2 = c) & (y^2 = a^2 * c + b) --> a * c <= y * x"
   7.134 -  by (sos csdp)
   7.135 +  by sos
   7.136  lemma "abs(x - z) <= e & abs(y - z) <= e & 0 <= u & 0 <= v & (u + v = 1) --> abs((u * x + v * y) - z) <= (e::real)"
   7.137 -  by (sos csdp)
   7.138 +  by sos
   7.139  
   7.140  
   7.141  (* lemma "((x::real) - y - 2 * x^4 = 0) & 0 <= x & x <= 2 & 0 <= y & y <= 3 --> y^2 - 7 * y - 12 * x + 17 >= 0" by sos *) (* Too hard?*)
   7.142  
   7.143  lemma "(0::real) <= x --> (1 + x + x^2)/(1 + x^2) <= 1 + x"
   7.144 -  by (sos csdp)
   7.145 +  by sos
   7.146  
   7.147  lemma "(0::real) <= x --> 1 - x <= 1 / (1 + x + x^2)"
   7.148 -  by (sos csdp)
   7.149 +  by sos
   7.150  
   7.151  lemma "(x::real) <= 1 / 2 --> - x - 2 * x^2 <= - x / (1 - x)"
   7.152 -  by (sos csdp)
   7.153 +  by sos
   7.154  
   7.155  lemma "4*r^2 = p^2 - 4*q & r >= (0::real) & x^2 + p*x + q = 0 --> 2*(x::real) = - p + 2*r | 2*x = -p - 2*r"
   7.156 -  by (sos csdp)
   7.157 +  by sos
   7.158  
   7.159  end
   7.160  
     8.1 --- a/src/HOL/ex/SOS_Cert.thy	Wed Oct 08 10:15:04 2014 +0200
     8.2 +++ b/src/HOL/ex/SOS_Cert.thy	Wed Oct 08 11:09:17 2014 +0200
     8.3 @@ -10,121 +10,121 @@
     8.4  begin
     8.5  
     8.6  lemma "(3::real) * x + 7 * a < 4 & 3 < 2 * x \<Longrightarrow> a < 0"
     8.7 -  by (sos_cert "((R<1 + (((A<1 * R<1) * (R<2 * [1]^2)) + (((A<0 * R<1) * (R<3 * [1]^2)) + ((A<=0 * R<1) * (R<14 * [1]^2))))))")
     8.8 +  by (sos "((R<1 + (((A<1 * R<1) * (R<2 * [1]^2)) + (((A<0 * R<1) * (R<3 * [1]^2)) + ((A<=0 * R<1) * (R<14 * [1]^2))))))")
     8.9  
    8.10  lemma "a1 >= 0 & a2 >= 0 \<and> (a1 * a1 + a2 * a2 = b1 * b1 + b2 * b2 + 2) \<and> (a1 * b1 + a2 * b2 = 0) --> a1 * a2 - b1 * b2 >= (0::real)"
    8.11 -  by (sos_cert "(((A<0 * R<1) + (([~1/2*a1*b2 + ~1/2*a2*b1] * A=0) + (([~1/2*a1*a2 + 1/2*b1*b2] * A=1) + (((A<0 * R<1) * ((R<1/2 * [b2]^2) + (R<1/2 * [b1]^2))) + ((A<=0 * (A<=1 * R<1)) * ((R<1/2 * [b2]^2) + ((R<1/2 * [b1]^2) + ((R<1/2 * [a2]^2) + (R<1/2 * [a1]^2))))))))))")
    8.12 +  by (sos "(((A<0 * R<1) + (([~1/2*a1*b2 + ~1/2*a2*b1] * A=0) + (([~1/2*a1*a2 + 1/2*b1*b2] * A=1) + (((A<0 * R<1) * ((R<1/2 * [b2]^2) + (R<1/2 * [b1]^2))) + ((A<=0 * (A<=1 * R<1)) * ((R<1/2 * [b2]^2) + ((R<1/2 * [b1]^2) + ((R<1/2 * [a2]^2) + (R<1/2 * [a1]^2))))))))))")
    8.13  
    8.14  lemma "(3::real) * x + 7 * a < 4 & 3 < 2 * x --> a < 0"
    8.15 -  by (sos_cert "((R<1 + (((A<1 * R<1) * (R<2 * [1]^2)) + (((A<0 * R<1) * (R<3 * [1]^2)) + ((A<=0 * R<1) * (R<14 * [1]^2))))))")
    8.16 +  by (sos "((R<1 + (((A<1 * R<1) * (R<2 * [1]^2)) + (((A<0 * R<1) * (R<3 * [1]^2)) + ((A<=0 * R<1) * (R<14 * [1]^2))))))")
    8.17  
    8.18  lemma "(0::real) <= x & x <= 1 & 0 <= y & y <= 1  --> x^2 + y^2 < 1 |(x - 1)^2 + y^2 < 1 | x^2 + (y - 1)^2 < 1 | (x - 1)^2 + (y - 1)^2 < 1"
    8.19 -  by (sos_cert "((R<1 + (((A<=3 * (A<=4 * R<1)) * (R<1 * [1]^2)) + (((A<=2 * (A<=7 * R<1)) * (R<1 * [1]^2)) + (((A<=1 * (A<=6 * R<1)) * (R<1 * [1]^2)) + ((A<=0 * (A<=5 * R<1)) * (R<1 * [1]^2)))))))")
    8.20 +  by (sos "((R<1 + (((A<=3 * (A<=4 * R<1)) * (R<1 * [1]^2)) + (((A<=2 * (A<=7 * R<1)) * (R<1 * [1]^2)) + (((A<=1 * (A<=6 * R<1)) * (R<1 * [1]^2)) + ((A<=0 * (A<=5 * R<1)) * (R<1 * [1]^2)))))))")
    8.21  
    8.22  lemma "(0::real) <= x & 0 <= y & 0 <= z & x + y + z <= 3 --> x * y + x * z + y * z >= 3 * x * y * z"
    8.23 -  by (sos_cert "(((A<0 * R<1) + (((A<0 * R<1) * (R<1/2 * [1]^2)) + (((A<=2 * R<1) * (R<1/2 * [~1*x + y]^2)) + (((A<=1 * R<1) * (R<1/2 * [~1*x + z]^2)) + (((A<=1 * (A<=2 * (A<=3 * R<1))) * (R<1/2 * [1]^2)) + (((A<=0 * R<1) * (R<1/2 * [~1*y + z]^2)) + (((A<=0 * (A<=2 * (A<=3 * R<1))) * (R<1/2 * [1]^2)) + ((A<=0 * (A<=1 * (A<=3 * R<1))) * (R<1/2 * [1]^2))))))))))")
    8.24 +  by (sos "(((A<0 * R<1) + (((A<0 * R<1) * (R<1/2 * [1]^2)) + (((A<=2 * R<1) * (R<1/2 * [~1*x + y]^2)) + (((A<=1 * R<1) * (R<1/2 * [~1*x + z]^2)) + (((A<=1 * (A<=2 * (A<=3 * R<1))) * (R<1/2 * [1]^2)) + (((A<=0 * R<1) * (R<1/2 * [~1*y + z]^2)) + (((A<=0 * (A<=2 * (A<=3 * R<1))) * (R<1/2 * [1]^2)) + ((A<=0 * (A<=1 * (A<=3 * R<1))) * (R<1/2 * [1]^2))))))))))")
    8.25  
    8.26  lemma "((x::real)^2 + y^2 + z^2 = 1) --> (x + y + z)^2 <= 3"
    8.27 -  by (sos_cert "(((A<0 * R<1) + (([~3] * A=0) + (R<1 * ((R<2 * [~1/2*x + ~1/2*y + z]^2) + (R<3/2 * [~1*x + y]^2))))))")
    8.28 +  by (sos "(((A<0 * R<1) + (([~3] * A=0) + (R<1 * ((R<2 * [~1/2*x + ~1/2*y + z]^2) + (R<3/2 * [~1*x + y]^2))))))")
    8.29  
    8.30  lemma "(w^2 + x^2 + y^2 + z^2 = 1) --> (w + x + y + z)^2 <= (4::real)"
    8.31 -  by (sos_cert "(((A<0 * R<1) + (([~4] * A=0) + (R<1 * ((R<3 * [~1/3*w + ~1/3*x + ~1/3*y + z]^2) + ((R<8/3 * [~1/2*w + ~1/2*x + y]^2) + (R<2 * [~1*w + x]^2)))))))")
    8.32 +  by (sos "(((A<0 * R<1) + (([~4] * A=0) + (R<1 * ((R<3 * [~1/3*w + ~1/3*x + ~1/3*y + z]^2) + ((R<8/3 * [~1/2*w + ~1/2*x + y]^2) + (R<2 * [~1*w + x]^2)))))))")
    8.33  
    8.34  lemma "(x::real) >= 1 & y >= 1 --> x * y >= x + y - 1"
    8.35 -  by (sos_cert "(((A<0 * R<1) + ((A<=0 * (A<=1 * R<1)) * (R<1 * [1]^2))))")
    8.36 +  by (sos "(((A<0 * R<1) + ((A<=0 * (A<=1 * R<1)) * (R<1 * [1]^2))))")
    8.37  
    8.38  lemma "(x::real) > 1 & y > 1 --> x * y > x + y - 1"
    8.39 -  by (sos_cert "((((A<0 * A<1) * R<1) + ((A<=0 * R<1) * (R<1 * [1]^2))))")
    8.40 +  by (sos "((((A<0 * A<1) * R<1) + ((A<=0 * R<1) * (R<1 * [1]^2))))")
    8.41  
    8.42  lemma "abs(x) <= 1 --> abs(64 * x^7 - 112 * x^5 + 56 * x^3 - 7 * x) <= (1::real)"
    8.43 -  by (sos_cert "((((A<0 * R<1) + ((A<=1 * R<1) * (R<1 * [~8*x^3 + ~4*x^2 + 4*x + 1]^2)))) & ((((A<0 * A<1) * R<1) + ((A<=1 * (A<0 * R<1)) * (R<1 * [8*x^3 + ~4*x^2 + ~4*x + 1]^2)))))")
    8.44 +  by (sos "((((A<0 * R<1) + ((A<=1 * R<1) * (R<1 * [~8*x^3 + ~4*x^2 + 4*x + 1]^2)))) & ((((A<0 * A<1) * R<1) + ((A<=1 * (A<0 * R<1)) * (R<1 * [8*x^3 + ~4*x^2 + ~4*x + 1]^2)))))")
    8.45  
    8.46  
    8.47  text \<open>One component of denominator in dodecahedral example.\<close>
    8.48  
    8.49  lemma "2 <= x & x <= 125841 / 50000 & 2 <= y & y <= 125841 / 50000 & 2 <= z & z <= 125841 / 50000 --> 2 * (x * z + x * y + y * z) - (x * x + y * y + z * z) >= (0::real)"
    8.50 -  by (sos_cert "(((A<0 * R<1) + ((R<1 * ((R<5749028157/5000000000 * [~25000/222477*x + ~25000/222477*y + ~25000/222477*z + 1]^2) + ((R<864067/1779816 * [419113/864067*x + 419113/864067*y + z]^2) + ((R<320795/864067 * [419113/1283180*x + y]^2) + (R<1702293/5132720 * [x]^2))))) + (((A<=4 * (A<=5 * R<1)) * (R<3/2 * [1]^2)) + (((A<=3 * (A<=5 * R<1)) * (R<1/2 * [1]^2)) + (((A<=2 * (A<=4 * R<1)) * (R<1 * [1]^2)) + (((A<=2 * (A<=3 * R<1)) * (R<3/2 * [1]^2)) + (((A<=1 * (A<=5 * R<1)) * (R<1/2 * [1]^2)) + (((A<=1 * (A<=3 * R<1)) * (R<1/2 * [1]^2)) + (((A<=0 * (A<=4 * R<1)) * (R<1 * [1]^2)) + (((A<=0 * (A<=2 * R<1)) * (R<1 * [1]^2)) + ((A<=0 * (A<=1 * R<1)) * (R<3/2 * [1]^2)))))))))))))")
    8.51 +  by (sos "(((A<0 * R<1) + ((R<1 * ((R<5749028157/5000000000 * [~25000/222477*x + ~25000/222477*y + ~25000/222477*z + 1]^2) + ((R<864067/1779816 * [419113/864067*x + 419113/864067*y + z]^2) + ((R<320795/864067 * [419113/1283180*x + y]^2) + (R<1702293/5132720 * [x]^2))))) + (((A<=4 * (A<=5 * R<1)) * (R<3/2 * [1]^2)) + (((A<=3 * (A<=5 * R<1)) * (R<1/2 * [1]^2)) + (((A<=2 * (A<=4 * R<1)) * (R<1 * [1]^2)) + (((A<=2 * (A<=3 * R<1)) * (R<3/2 * [1]^2)) + (((A<=1 * (A<=5 * R<1)) * (R<1/2 * [1]^2)) + (((A<=1 * (A<=3 * R<1)) * (R<1/2 * [1]^2)) + (((A<=0 * (A<=4 * R<1)) * (R<1 * [1]^2)) + (((A<=0 * (A<=2 * R<1)) * (R<1 * [1]^2)) + ((A<=0 * (A<=1 * R<1)) * (R<3/2 * [1]^2)))))))))))))")
    8.52  
    8.53  
    8.54  text \<open>Over a larger but simpler interval.\<close>
    8.55  
    8.56  lemma "(2::real) <= x & x <= 4 & 2 <= y & y <= 4 & 2 <= z & z <= 4 --> 0 <= 2 * (x * z + x * y + y * z) - (x * x + y * y + z * z)"
    8.57 -  by (sos_cert "((R<1 + ((R<1 * ((R<1 * [~1/6*x + ~1/6*y + ~1/6*z + 1]^2) + ((R<1/18 * [~1/2*x + ~1/2*y + z]^2) + (R<1/24 * [~1*x + y]^2)))) + (((A<0 * R<1) * (R<1/12 * [1]^2)) + (((A<=4 * (A<=5 * R<1)) * (R<1/6 * [1]^2)) + (((A<=2 * (A<=4 * R<1)) * (R<1/6 * [1]^2)) + (((A<=2 * (A<=3 * R<1)) * (R<1/6 * [1]^2)) + (((A<=0 * (A<=4 * R<1)) * (R<1/6 * [1]^2)) + (((A<=0 * (A<=2 * R<1)) * (R<1/6 * [1]^2)) + ((A<=0 * (A<=1 * R<1)) * (R<1/6 * [1]^2)))))))))))")
    8.58 +  by (sos "((R<1 + ((R<1 * ((R<1 * [~1/6*x + ~1/6*y + ~1/6*z + 1]^2) + ((R<1/18 * [~1/2*x + ~1/2*y + z]^2) + (R<1/24 * [~1*x + y]^2)))) + (((A<0 * R<1) * (R<1/12 * [1]^2)) + (((A<=4 * (A<=5 * R<1)) * (R<1/6 * [1]^2)) + (((A<=2 * (A<=4 * R<1)) * (R<1/6 * [1]^2)) + (((A<=2 * (A<=3 * R<1)) * (R<1/6 * [1]^2)) + (((A<=0 * (A<=4 * R<1)) * (R<1/6 * [1]^2)) + (((A<=0 * (A<=2 * R<1)) * (R<1/6 * [1]^2)) + ((A<=0 * (A<=1 * R<1)) * (R<1/6 * [1]^2)))))))))))")
    8.59  
    8.60  
    8.61  text \<open>We can do 12. I think 12 is a sharp bound; see PP's certificate.\<close>
    8.62  
    8.63  lemma "2 <= (x::real) & x <= 4 & 2 <= y & y <= 4 & 2 <= z & z <= 4 --> 12 <= 2 * (x * z + x * y + y * z) - (x * x + y * y + z * z)"
    8.64 -  by (sos_cert "(((A<0 * R<1) + (((A<=4 * R<1) * (R<2/3 * [1]^2)) + (((A<=4 * (A<=5 * R<1)) * (R<1 * [1]^2)) + (((A<=3 * (A<=4 * R<1)) * (R<1/3 * [1]^2)) + (((A<=2 * R<1) * (R<2/3 * [1]^2)) + (((A<=2 * (A<=5 * R<1)) * (R<1/3 * [1]^2)) + (((A<=2 * (A<=4 * R<1)) * (R<8/3 * [1]^2)) + (((A<=2 * (A<=3 * R<1)) * (R<1 * [1]^2)) + (((A<=1 * (A<=4 * R<1)) * (R<1/3 * [1]^2)) + (((A<=1 * (A<=2 * R<1)) * (R<1/3 * [1]^2)) + (((A<=0 * R<1) * (R<2/3 * [1]^2)) + (((A<=0 * (A<=5 * R<1)) * (R<1/3 * [1]^2)) + (((A<=0 * (A<=4 * R<1)) * (R<8/3 * [1]^2)) + (((A<=0 * (A<=3 * R<1)) * (R<1/3 * [1]^2)) + (((A<=0 * (A<=2 * R<1)) * (R<8/3 * [1]^2)) + ((A<=0 * (A<=1 * R<1)) * (R<1 * [1]^2))))))))))))))))))")
    8.65 +  by (sos "(((A<0 * R<1) + (((A<=4 * R<1) * (R<2/3 * [1]^2)) + (((A<=4 * (A<=5 * R<1)) * (R<1 * [1]^2)) + (((A<=3 * (A<=4 * R<1)) * (R<1/3 * [1]^2)) + (((A<=2 * R<1) * (R<2/3 * [1]^2)) + (((A<=2 * (A<=5 * R<1)) * (R<1/3 * [1]^2)) + (((A<=2 * (A<=4 * R<1)) * (R<8/3 * [1]^2)) + (((A<=2 * (A<=3 * R<1)) * (R<1 * [1]^2)) + (((A<=1 * (A<=4 * R<1)) * (R<1/3 * [1]^2)) + (((A<=1 * (A<=2 * R<1)) * (R<1/3 * [1]^2)) + (((A<=0 * R<1) * (R<2/3 * [1]^2)) + (((A<=0 * (A<=5 * R<1)) * (R<1/3 * [1]^2)) + (((A<=0 * (A<=4 * R<1)) * (R<8/3 * [1]^2)) + (((A<=0 * (A<=3 * R<1)) * (R<1/3 * [1]^2)) + (((A<=0 * (A<=2 * R<1)) * (R<8/3 * [1]^2)) + ((A<=0 * (A<=1 * R<1)) * (R<1 * [1]^2))))))))))))))))))")
    8.66  
    8.67  
    8.68  text \<open>Inequality from sci.math (see "Leon-Sotelo, por favor").\<close>
    8.69  
    8.70  lemma "0 <= (x::real) & 0 <= y & (x * y = 1) --> x + y <= x^2 + y^2"
    8.71 -  by (sos_cert "(((A<0 * R<1) + (([1] * A=0) + (R<1 * ((R<1 * [~1/2*x + ~1/2*y + 1]^2) + (R<3/4 * [~1*x + y]^2))))))")
    8.72 +  by (sos "(((A<0 * R<1) + (([1] * A=0) + (R<1 * ((R<1 * [~1/2*x + ~1/2*y + 1]^2) + (R<3/4 * [~1*x + y]^2))))))")
    8.73  
    8.74  lemma "0 <= (x::real) & 0 <= y & (x * y = 1) --> x * y * (x + y) <= x^2 + y^2"
    8.75 -  by (sos_cert "(((A<0 * R<1) + (([~1*x + ~1*y + 1] * A=0) + (R<1 * ((R<1 * [~1/2*x + ~1/2*y + 1]^2) + (R<3/4 * [~1*x + y]^2))))))")
    8.76 +  by (sos "(((A<0 * R<1) + (([~1*x + ~1*y + 1] * A=0) + (R<1 * ((R<1 * [~1/2*x + ~1/2*y + 1]^2) + (R<3/4 * [~1*x + y]^2))))))")
    8.77  
    8.78  lemma "0 <= (x::real) & 0 <= y --> x * y * (x + y)^2 <= (x^2 + y^2)^2"
    8.79 -  by (sos_cert "(((A<0 * R<1) + (R<1 * ((R<1 * [~1/2*x^2 + y^2 + ~1/2*x*y]^2) + (R<3/4 * [~1*x^2 + x*y]^2)))))")
    8.80 +  by (sos "(((A<0 * R<1) + (R<1 * ((R<1 * [~1/2*x^2 + y^2 + ~1/2*x*y]^2) + (R<3/4 * [~1*x^2 + x*y]^2)))))")
    8.81  
    8.82  lemma "(0::real) <= a & 0 <= b & 0 <= c & c * (2 * a + b)^3/ 27 <= x \<longrightarrow> c * a^2 * b <= x"
    8.83 -  by (sos_cert "(((A<0 * R<1) + (((A<=3 * R<1) * (R<1 * [1]^2)) + (((A<=1 * (A<=2 * R<1)) * (R<1/27 * [~1*a + b]^2)) + ((A<=0 * (A<=2 * R<1)) * (R<8/27 * [~1*a + b]^2))))))")
    8.84 +  by (sos "(((A<0 * R<1) + (((A<=3 * R<1) * (R<1 * [1]^2)) + (((A<=1 * (A<=2 * R<1)) * (R<1/27 * [~1*a + b]^2)) + ((A<=0 * (A<=2 * R<1)) * (R<8/27 * [~1*a + b]^2))))))")
    8.85  
    8.86  lemma "(0::real) < x --> 0 < 1 + x + x^2"
    8.87 -  by (sos_cert "((R<1 + ((R<1 * (R<1 * [x]^2)) + (((A<0 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2))))))")
    8.88 +  by (sos "((R<1 + ((R<1 * (R<1 * [x]^2)) + (((A<0 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2))))))")
    8.89  
    8.90  lemma "(0::real) <= x --> 0 < 1 + x + x^2"
    8.91 -  by (sos_cert "((R<1 + ((R<1 * (R<1 * [x]^2)) + (((A<=1 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2))))))")
    8.92 +  by (sos "((R<1 + ((R<1 * (R<1 * [x]^2)) + (((A<=1 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2))))))")
    8.93  
    8.94  lemma "(0::real) < 1 + x^2"
    8.95 -  by (sos_cert "((R<1 + ((R<1 * (R<1 * [x]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2)))))")
    8.96 +  by (sos "((R<1 + ((R<1 * (R<1 * [x]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2)))))")
    8.97  
    8.98  lemma "(0::real) <= 1 + 2 * x + x^2"
    8.99 -  by (sos_cert "(((A<0 * R<1) + (R<1 * (R<1 * [x + 1]^2))))")
   8.100 +  by (sos "(((A<0 * R<1) + (R<1 * (R<1 * [x + 1]^2))))")
   8.101  
   8.102  lemma "(0::real) < 1 + abs x"
   8.103 -  by (sos_cert "((R<1 + (((A<=1 * R<1) * (R<1/2 * [1]^2)) + ((A<=0 * R<1) * (R<1/2 * [1]^2)))))")
   8.104 +  by (sos "((R<1 + (((A<=1 * R<1) * (R<1/2 * [1]^2)) + ((A<=0 * R<1) * (R<1/2 * [1]^2)))))")
   8.105  
   8.106  lemma "(0::real) < 1 + (1 + x)^2 * (abs x)"
   8.107 -  by (sos_cert "(((R<1 + (((A<=1 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [x + 1]^2))))) & ((R<1 + (((A<0 * R<1) * (R<1 * [x + 1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2))))))")
   8.108 +  by (sos "(((R<1 + (((A<=1 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [x + 1]^2))))) & ((R<1 + (((A<0 * R<1) * (R<1 * [x + 1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2))))))")
   8.109  
   8.110  
   8.111  lemma "abs ((1::real) + x^2) = (1::real) + x^2"
   8.112 -  by (sos_cert "(() & (((R<1 + ((R<1 * (R<1 * [x]^2)) + ((A<1 * R<1) * (R<1/2 * [1]^2))))) & ((R<1 + ((R<1 * (R<1 * [x]^2)) + ((A<0 * R<1) * (R<1 * [1]^2)))))))")
   8.113 +  by (sos "(() & (((R<1 + ((R<1 * (R<1 * [x]^2)) + ((A<1 * R<1) * (R<1/2 * [1]^2))))) & ((R<1 + ((R<1 * (R<1 * [x]^2)) + ((A<0 * R<1) * (R<1 * [1]^2)))))))")
   8.114  lemma "(3::real) * x + 7 * a < 4 \<and> 3 < 2 * x \<longrightarrow> a < 0"
   8.115 -  by (sos_cert "((R<1 + (((A<1 * R<1) * (R<2 * [1]^2)) + (((A<0 * R<1) * (R<3 * [1]^2)) + ((A<=0 * R<1) * (R<14 * [1]^2))))))")
   8.116 +  by (sos "((R<1 + (((A<1 * R<1) * (R<2 * [1]^2)) + (((A<0 * R<1) * (R<3 * [1]^2)) + ((A<=0 * R<1) * (R<14 * [1]^2))))))")
   8.117  
   8.118  lemma "(0::real) < x --> 1 < y --> y * x <= z --> x < z"
   8.119 -  by (sos_cert "((((A<0 * A<1) * R<1) + (((A<=1 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2)))))")
   8.120 +  by (sos "((((A<0 * A<1) * R<1) + (((A<=1 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2)))))")
   8.121  lemma "(1::real) < x --> x^2 < y --> 1 < y"
   8.122 -  by (sos_cert "((((A<0 * A<1) * R<1) + ((R<1 * ((R<1/10 * [~2*x + y + 1]^2) + (R<1/10 * [~1*x + y]^2))) + (((A<1 * R<1) * (R<1/2 * [1]^2)) + (((A<0 * R<1) * (R<1 * [x]^2)) + (((A<=0 * R<1) * ((R<1/10 * [x + 1]^2) + (R<1/10 * [x]^2))) + (((A<=0 * (A<1 * R<1)) * (R<1/5 * [1]^2)) + ((A<=0 * (A<0 * R<1)) * (R<1/5 * [1]^2)))))))))")
   8.123 +  by (sos "((((A<0 * A<1) * R<1) + ((R<1 * ((R<1/10 * [~2*x + y + 1]^2) + (R<1/10 * [~1*x + y]^2))) + (((A<1 * R<1) * (R<1/2 * [1]^2)) + (((A<0 * R<1) * (R<1 * [x]^2)) + (((A<=0 * R<1) * ((R<1/10 * [x + 1]^2) + (R<1/10 * [x]^2))) + (((A<=0 * (A<1 * R<1)) * (R<1/5 * [1]^2)) + ((A<=0 * (A<0 * R<1)) * (R<1/5 * [1]^2)))))))))")
   8.124  lemma "(b::real)^2 < 4 * a * c --> ~(a * x^2 + b * x + c = 0)"
   8.125 -  by (sos_cert "(((A<0 * R<1) + (R<1 * (R<1 * [2*a*x + b]^2))))")
   8.126 +  by (sos "(((A<0 * R<1) + (R<1 * (R<1 * [2*a*x + b]^2))))")
   8.127  lemma "(b::real)^2 < 4 * a * c --> ~(a * x^2 + b * x + c = 0)"
   8.128 -  by (sos_cert "(((A<0 * R<1) + (R<1 * (R<1 * [2*a*x + b]^2))))")
   8.129 +  by (sos "(((A<0 * R<1) + (R<1 * (R<1 * [2*a*x + b]^2))))")
   8.130  lemma "((a::real) * x^2 + b * x + c = 0) --> b^2 >= 4 * a * c"
   8.131 -  by (sos_cert "(((A<0 * R<1) + (R<1 * (R<1 * [2*a*x + b]^2))))")
   8.132 +  by (sos "(((A<0 * R<1) + (R<1 * (R<1 * [2*a*x + b]^2))))")
   8.133  lemma "(0::real) <= b & 0 <= c & 0 <= x & 0 <= y & (x^2 = c) & (y^2 = a^2 * c + b) --> a * c <= y * x"
   8.134 -  by (sos_cert "(((A<0 * (A<0 * R<1)) + (((A<=2 * (A<=3 * (A<0 * R<1))) * (R<2 * [1]^2)) + ((A<=0 * (A<=1 * R<1)) * (R<1 * [1]^2)))))")
   8.135 +  by (sos "(((A<0 * (A<0 * R<1)) + (((A<=2 * (A<=3 * (A<0 * R<1))) * (R<2 * [1]^2)) + ((A<=0 * (A<=1 * R<1)) * (R<1 * [1]^2)))))")
   8.136  lemma "abs(x - z) <= e & abs(y - z) <= e & 0 <= u & 0 <= v & (u + v = 1) --> abs((u * x + v * y) - z) <= (e::real)"
   8.137 -  by (sos_cert "((((A<0 * R<1) + (((A<=3 * (A<=6 * R<1)) * (R<1 * [1]^2)) + ((A<=1 * (A<=5 * R<1)) * (R<1 * [1]^2))))) & ((((A<0 * A<1) * R<1) + (((A<=3 * (A<=5 * (A<0 * R<1))) * (R<1 * [1]^2)) + ((A<=1 * (A<=4 * (A<0 * R<1))) * (R<1 * [1]^2))))))")
   8.138 +  by (sos "((((A<0 * R<1) + (((A<=3 * (A<=6 * R<1)) * (R<1 * [1]^2)) + ((A<=1 * (A<=5 * R<1)) * (R<1 * [1]^2))))) & ((((A<0 * A<1) * R<1) + (((A<=3 * (A<=5 * (A<0 * R<1))) * (R<1 * [1]^2)) + ((A<=1 * (A<=4 * (A<0 * R<1))) * (R<1 * [1]^2))))))")
   8.139  
   8.140  
   8.141  (* lemma "((x::real) - y - 2 * x^4 = 0) & 0 <= x & x <= 2 & 0 <= y & y <= 3 --> y^2 - 7 * y - 12 * x + 17 >= 0" by sos *) (* Too hard?*)
   8.142  
   8.143  lemma "(0::real) <= x --> (1 + x + x^2)/(1 + x^2) <= 1 + x"
   8.144 -  by (sos_cert "(((((A<0 * A<1) * R<1) + ((A<=0 * (A<0 * R<1)) * (R<1 * [x]^2)))) & ((R<1 + ((R<1 * (R<1 * [x]^2)) + ((A<0 * R<1) * (R<1 * [1]^2))))))")
   8.145 +  by (sos "(((((A<0 * A<1) * R<1) + ((A<=0 * (A<0 * R<1)) * (R<1 * [x]^2)))) & ((R<1 + ((R<1 * (R<1 * [x]^2)) + ((A<0 * R<1) * (R<1 * [1]^2))))))")
   8.146  
   8.147  lemma "(0::real) <= x --> 1 - x <= 1 / (1 + x + x^2)"
   8.148 -  by (sos_cert "(((R<1 + (([~4/3] * A=0) + ((R<1 * ((R<1/3 * [3/2*x + 1]^2) + (R<7/12 * [x]^2))) + ((A<=0 * R<1) * (R<1/3 * [1]^2)))))) & (((((A<0 * A<1) * R<1) + ((A<=0 * (A<0 * R<1)) * (R<1 * [x]^2)))) & ((R<1 + ((R<1 * (R<1 * [x]^2)) + (((A<0 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2))))))))")
   8.149 +  by (sos "(((R<1 + (([~4/3] * A=0) + ((R<1 * ((R<1/3 * [3/2*x + 1]^2) + (R<7/12 * [x]^2))) + ((A<=0 * R<1) * (R<1/3 * [1]^2)))))) & (((((A<0 * A<1) * R<1) + ((A<=0 * (A<0 * R<1)) * (R<1 * [x]^2)))) & ((R<1 + ((R<1 * (R<1 * [x]^2)) + (((A<0 * R<1) * (R<1 * [1]^2)) + ((A<=0 * R<1) * (R<1 * [1]^2))))))))")
   8.150  
   8.151  lemma "(x::real) <= 1 / 2 --> - x - 2 * x^2 <= - x / (1 - x)"
   8.152 -  by (sos_cert "((((A<0 * A<1) * R<1) + ((A<=0 * (A<0 * R<1)) * (R<1 * [x]^2))))")
   8.153 +  by (sos "((((A<0 * A<1) * R<1) + ((A<=0 * (A<0 * R<1)) * (R<1 * [x]^2))))")
   8.154  
   8.155  lemma "4*r^2 = p^2 - 4*q & r >= (0::real) & x^2 + p*x + q = 0 --> 2*(x::real) = - p + 2*r | 2*x = -p - 2*r"
   8.156 -  by (sos_cert "((((((A<0 * A<1) * R<1) + ([~4] * A=0))) & ((((A<0 * A<1) * R<1) + ([4] * A=0)))) & (((((A<0 * A<1) * R<1) + ([4] * A=0))) & ((((A<0 * A<1) * R<1) + ([~4] * A=0)))))")
   8.157 +  by (sos "((((((A<0 * A<1) * R<1) + ([~4] * A=0))) & ((((A<0 * A<1) * R<1) + ([4] * A=0)))) & (((((A<0 * A<1) * R<1) + ([4] * A=0))) & ((((A<0 * A<1) * R<1) + ([~4] * A=0)))))")
   8.158  
   8.159  end
   8.160  
     9.1 --- a/src/HOL/ex/SOS_Remote.thy	Wed Oct 08 10:15:04 2014 +0200
     9.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     9.3 @@ -1,37 +0,0 @@
     9.4 -(*  Title:      HOL/ex/SOS_Remote.thy
     9.5 -    Author:     Amine Chaieb, University of Cambridge
     9.6 -    Author:     Philipp Meyer, TU Muenchen
     9.7 -
     9.8 -Examples for Sum_of_Squares: remote CSDP server.
     9.9 -*)
    9.10 -
    9.11 -theory SOS_Remote
    9.12 -imports "~~/src/HOL/Library/Sum_of_Squares"
    9.13 -begin
    9.14 -
    9.15 -lemma "(3::real) * x + 7 * a < 4 & 3 < 2 * x \<Longrightarrow> a < 0"
    9.16 -  by (sos remote_csdp)
    9.17 -
    9.18 -lemma "a1 >= 0 & a2 >= 0 \<and> (a1 * a1 + a2 * a2 = b1 * b1 + b2 * b2 + 2) \<and> (a1 * b1 + a2 * b2 = 0) --> a1 * a2 - b1 * b2 >= (0::real)"
    9.19 -  by (sos remote_csdp)
    9.20 -
    9.21 -lemma "(3::real) * x + 7 * a < 4 & 3 < 2 * x --> a < 0"
    9.22 -  by (sos remote_csdp)
    9.23 -
    9.24 -lemma "(0::real) <= x & x <= 1 & 0 <= y & y <= 1  --> x^2 + y^2 < 1 |(x - 1)^2 + y^2 < 1 | x^2 + (y - 1)^2 < 1 | (x - 1)^2 + (y - 1)^2 < 1"
    9.25 -  by (sos remote_csdp)
    9.26 -
    9.27 -lemma "(0::real) <= x & 0 <= y & 0 <= z & x + y + z <= 3 --> x * y + x * z + y * z >= 3 * x * y * z"
    9.28 -  by (sos remote_csdp)
    9.29 -
    9.30 -lemma "((x::real)^2 + y^2 + z^2 = 1) --> (x + y + z)^2 <= 3"
    9.31 -  by (sos remote_csdp)
    9.32 -
    9.33 -lemma "(w^2 + x^2 + y^2 + z^2 = 1) --> (w + x + y + z)^2 <= (4::real)"
    9.34 -  by (sos remote_csdp)
    9.35 -
    9.36 -lemma "(x::real) >= 1 & y >= 1 --> x * y >= x + y - 1"
    9.37 -  by (sos remote_csdp)
    9.38 -
    9.39 -end
    9.40 -