Why is this simple Z3 proof so slow? -

the following z3 code times out on online repl:

; want function (declare-fun f (int) int)  ; want linear (assert (forall ((a int) (b int)) (   = (+ (f a) (f b)) (f (+ b)) )))  ; want f(2) == 4 (assert (= (f 2) 4))  ; timeout :( (check-sat) 

so version, looking function on reals:

(declare-fun f (real) real) (assert (forall ((a real) (b real)) (   = (+ (f a) (f b)) (f (+ b)) ))) (assert (= (f 2) 4)) (check-sat) 

it's faster when give contradiction:

(declare-fun f (real) real) (assert (forall ((a real) (b real)) (   = (+ (f a) (f b)) (f (+ b)) ))) (assert (= (f 2) 4)) (assert (= (f 4) 7)) (check-sat) 

i'm quite unknowledgeable theorem provers. slow here? prover having lots of trouble proving linear functions f(2) = 4 exist?

the slowness due many quantifier instantiations, caused problematic patterns/triggers. if don't know these yet, have @ corresponding section of z3 guide.

bottom line: patterns syntactic heuristic, indicating smt solver when instantiate quantifier. patterns must cover quantified variables , interpreted functions such addition (+) not allowed in patterns. matching loop situation in every quantifier instantiation gives rise further quantifier instantiations.

in case, z3 picks pattern set :pattern ((f a) (f b)) (since don't explicitly provide patterns). suggests z3 instantiate quantifier every a, b ground terms (f a) , (f b) have occurred in current proof search. initially, proof search contains (f 2); hence, quantifier can instantiated a, b bound 2, 2. yields (f (+ 2 2)), can used instantiate quantifier once more (and in combination (f 2)). z3 stuck in matching loop.

here snippet arguing point:

(set-option :smt.qi.profile true)  (declare-fun f (int) int)  (declare-fun t (int int) bool) ; dummy trigger function  (assert (forall ((a int) (b int)) (!    (= (+ (f a) (f b)) (f (+ b)))   :pattern ((f a) (f b))   ; :pattern ((t b)) )))  (assert (= (f 2) 4))  (set-option :timeout 5000) ; 5s enough (check-sat) (get-info :reason-unknown) (get-info :all-statistics) 

with explicitly provided pattern you'll original behaviour (modulo specified timeout). moreover, statistics report lots of instantiations of quantifier (and more still if increase timeout).

if comment first pattern , uncomment second, i.e. if "guard" quantifier dummy trigger won't show in proof search, z3 terminates immediately. z3 still report unknown, though, because "knowns" did not account quantified constraint (which requirement sat; , cannot show unsat).

it possible rewrite quantifiers in order have better triggering behaviour. z3 guide, example, illustrates in context of injective functions/inverse functions. maybe you'll able perform similar transformation here.