Proof of proveit.physics.quantum.QPE._delta_b_floor_diff_in_interval theorem¶

import proveit
theory = proveit.Theory() # the theorem's theory
from proveit import l, defaults
from proveit.numbers import subtract
from proveit.physics.quantum.QPE import _full_domain, _t, _two_pow_t, _two_pow__t_minus_one
from proveit.physics.quantum.QPE import (
    _delta_b_is_real, _scaled_delta_b_floor_in_interval,
    _t_in_natural_pos, _two_pow_t_is_nat_pos, _two_pow_t_minus_one_is_nat_pos)

%proving _delta_b_floor_diff_in_interval

# interesting issue here: cascading "side effect failures" leading to
# max recursion error if we haven't already imported at least one of the
# following: _full_domain, _t, _two_pow_t, _two_pow__t_minus_one
defaults.assumptions = _delta_b_floor_diff_in_interval.all_conditions()

# previously proven
_scaled_delta_b_floor_in_interval

scaled_delta_less_than_one = (
    _scaled_delta_b_floor_in_interval.derive_element_upper_bound())

scaled_delta_greatereq_than_zero = (
    _scaled_delta_b_floor_in_interval.derive_element_lower_bound())

# for convenience, name the product 2^t * delta
scaled_delta = _scaled_delta_b_floor_in_interval.element

# for convenience, name the difference 2^t * delta - ell
scaled_delta_minus_ell = subtract(scaled_delta, l)

_delta_b_is_real

# This allows a distribution() method to proceed further below
from proveit import b
from proveit.physics.quantum.QPE import _b_floor, _best_floor_is_int
_delta_b_floor_is_real = _delta_b_is_real.instantiate({b: _b_floor})

# for convenience, name the ell membership obj
ell_in_full_domain = defaults.assumptions[0]

ell_upper_bound = ell_in_full_domain.derive_element_upper_bound()

ell_lower_bound = ell_in_full_domain.derive_element_lower_bound()

Upper Bound¶

Develop upper bound, using information about the bounds on the individual pieces …

from proveit.numbers import one, Neg
negative_ell_upper_bound = ell_lower_bound.left_mult_both_sides(Neg(one))

# rewrite the bounding inequality so -ell is on the left
negative_ell_upper_bound = negative_ell_upper_bound.with_styles(direction='normal')

scaled_delta_minus_ell_upper_bound = (
    scaled_delta_minus_ell.deduce_bound(
        [scaled_delta_less_than_one, negative_ell_upper_bound]))

Divide through by $2^t$ and Simplify

upper_bound_judgment = scaled_delta_minus_ell_upper_bound.divide_both_sides(_two_pow_t)

upper_bound_one_half_02 = upper_bound_judgment.inner_expr().lhs.distribute()

Lower Bound¶

Develop lower bound using information about the bounds on the individual pieces …

# recall from earlier:
ell_upper_bound

negative_ell_lower_bound = ell_upper_bound.left_mult_both_sides(Neg(one))

# recall from earlier:
scaled_delta_minus_ell

scaled_delta_minus_ell_lower_bound = (
    scaled_delta_minus_ell.deduce_bound(
        [scaled_delta_greatereq_than_zero.with_styles(direction='reversed'),
         negative_ell_lower_bound]))

Divide through by $2^t$ and Simplify

lower_bound_judgment = scaled_delta_minus_ell_lower_bound.divide_both_sides(_two_pow_t)

_delta_b_floor_diff_in_interval may now be readily provable (assuming required theorems are usable).  Simply execute "%qed".

%qed

proveit.physics.quantum.QPE._delta_b_floor_diff_in_interval has been proven.

	step type	requirements	statement
0	generalization	1	⊢
1	instantiation	2, 3, 6, 4, 5	⊢
	: , : , :
2	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.in_IntervalCO
3	instantiation	170, 6	⊢
	:
4	instantiation	102, 79, 7	⊢
	: , :
5	instantiation	8, 9, 10	⊢
	: , :
6	instantiation	16, 138, 152, 100	⊢
	: , :
7	instantiation	170, 11	⊢
	:
8	theorem		⊢
	proveit.logic.booleans.conjunction.and_if_both
9	instantiation	13, 12, 15	⊢
	: , : , :
10	instantiation	13, 14, 15	⊢
	: , : , :
11	instantiation	16, 118, 96, 43	⊢
	: , :
12	instantiation	17, 96, 137, 21, 18, 23, 19^*	⊢
	: , : , :
13	theorem		⊢
	proveit.logic.equality.sub_right_side_into
14	instantiation	20, 96, 21, 157, 22, 23, 31^*	⊢
	: , : , :
15	instantiation	24, 25, 106, 78, 43, 26^*	⊢
	: , : , :
16	conjecture		⊢
	proveit.numbers.division.div_real_closure
17	conjecture		⊢
	proveit.numbers.division.weak_div_from_numer_bound__pos_denom
18	instantiation	27, 28, 29	⊢
	: , : , :
19	instantiation	30, 140, 78, 43, 31^*	⊢
	: , :
20	conjecture		⊢
	proveit.numbers.division.strong_div_from_numer_bound__pos_denom
21	instantiation	102, 46, 49	⊢
	: , :
22	instantiation	32, 33, 34	⊢
	: , : , :
23	instantiation	35, 125	⊢
	:
24	conjecture		⊢
	proveit.numbers.division.distribute_frac_through_subtract
25	instantiation	199, 160, 46	⊢
	: , : , :
26	instantiation	127, 36, 37	⊢
	: , : , :
27	conjecture		⊢
	proveit.numbers.ordering.transitivity_less_eq_less_eq
28	instantiation	48, 67, 137, 49, 38, 39^*	⊢
	: , : , :
29	instantiation	40, 49, 67, 46, 41	⊢
	: , : , :
30	conjecture		⊢
	proveit.numbers.division.neg_frac_neg_numerator
31	instantiation	42, 140, 78, 43, 44^*	⊢
	: , :
32	conjecture		⊢
	proveit.numbers.ordering.transitivity_less_less_eq
33	instantiation	45, 49, 46, 138, 47	⊢
	: , : , :
34	instantiation	48, 138, 49, 50, 51, 52^*	⊢
	: , : , :
35	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.natural_pos_is_pos
36	instantiation	53, 54, 55, 58, 56^*	⊢
	: , : , :
37	instantiation	57, 58	⊢
	:
38	instantiation	69, 161, 118, 157, 59, 71, 60^, 72^	⊢
	: , : , :
39	instantiation	61, 122	⊢
	:
40	conjecture		⊢
	proveit.numbers.addition.weak_bound_via_left_term_bound
41	instantiation	62, 67, 138, 68	⊢
	: , : , :
42	conjecture		⊢
	proveit.numbers.division.div_as_mult
43	instantiation	111, 125	⊢
	:
44	instantiation	127, 63, 64	⊢
	: , : , :
45	conjecture		⊢
	proveit.numbers.addition.strong_bound_via_left_term_bound
46	instantiation	65, 67, 138, 68	⊢
	: , : , :
47	instantiation	66, 67, 138, 68	⊢
	: , : , :
48	conjecture		⊢
	proveit.numbers.addition.weak_bound_via_right_term_bound
49	instantiation	170, 118	⊢
	:
50	instantiation	102, 157, 161	⊢
	: , :
51	instantiation	69, 161, 154, 118, 70, 71, 72^, 73^	⊢
	: , : , :
52	instantiation	127, 74, 75	⊢
	: , : , :
53	conjecture		⊢
	proveit.numbers.division.frac_cancel_left
54	instantiation	199, 130, 76	⊢
	: , : , :
55	instantiation	199, 130, 77	⊢
	: , : , :
56	instantiation	126, 78	⊢
	:
57	conjecture		⊢
	proveit.numbers.division.frac_one_denom
58	instantiation	199, 160, 79	⊢
	: , : , :
59	instantiation	80, 179, 194, 167	⊢
	: , : , :
60	instantiation	90, 123, 140, 81^*	⊢
	: , :
61	conjecture		⊢
	proveit.numbers.addition.elim_zero_left
62	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.interval_co_lower_bound
63	instantiation	119, 82	⊢
	: , : , :
64	instantiation	83, 133, 84, 159, 100, 85^*	⊢
	: , : , :
65	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.all_in_interval_co__is__real
66	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.interval_co_upper_bound
67	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.zero_is_real
68	conjecture		⊢
	proveit.physics.quantum.QPE._scaled_delta_b_floor_in_interval
69	conjecture		⊢
	proveit.numbers.multiplication.reversed_weak_bound_via_right_factor_bound
70	instantiation	86, 179, 194, 167	⊢
	: , : , :
71	instantiation	87, 88	⊢
	: , :
72	instantiation	90, 123, 106, 89^*	⊢
	: , :
73	instantiation	90, 123, 136, 91^*	⊢
	: , :
74	instantiation	141, 196, 185, 142, 92, 143, 123, 140, 148	⊢
	: , : , : , : , : , :
75	instantiation	146, 123, 140, 93	⊢
	: , : , :
76	instantiation	199, 150, 94	⊢
	: , : , :
77	instantiation	199, 150, 95	⊢
	: , : , :
78	instantiation	199, 160, 96	⊢
	: , : , :
79	instantiation	97, 98	⊢
	:
80	conjecture		⊢
	proveit.numbers.number_sets.integers.interval_upper_bound
81	instantiation	135, 140	⊢
	:
82	instantiation	99, 133, 171, 161, 100, 101^*	⊢
	: , : , :
83	conjecture		⊢
	proveit.numbers.exponentiation.product_of_real_powers
84	instantiation	102, 171, 161	⊢
	: , :
85	instantiation	127, 103, 104	⊢
	: , : , :
86	conjecture		⊢
	proveit.numbers.number_sets.integers.interval_lower_bound
87	conjecture		⊢
	proveit.numbers.ordering.relax_less
88	instantiation	105, 192	⊢
	:
89	instantiation	135, 106	⊢
	:
90	conjecture		⊢
	proveit.numbers.multiplication.mult_neg_left
91	instantiation	127, 107, 108	⊢
	: , : , :
92	instantiation	158	⊢
	: , :
93	instantiation	162	⊢
	:
94	instantiation	199, 163, 109	⊢
	: , : , :
95	instantiation	199, 163, 110	⊢
	: , : , :
96	instantiation	180, 181, 125	⊢
	: , : , :
97	conjecture		⊢
	proveit.physics.quantum.QPE._delta_b_is_real
98	conjecture		⊢
	proveit.physics.quantum.QPE._best_floor_is_int
99	conjecture		⊢
	proveit.numbers.exponentiation.real_power_of_real_power
100	instantiation	111, 175	⊢
	:
101	instantiation	112, 147, 123, 113^*	⊢
	: , :
102	conjecture		⊢
	proveit.numbers.addition.add_real_closure_bin
103	instantiation	119, 114	⊢
	: , : , :
104	instantiation	115, 116, 198, 117^*	⊢
	: , :
105	conjecture		⊢
	proveit.numbers.number_sets.integers.negative_if_in_neg_int
106	instantiation	199, 160, 118	⊢
	: , : , :
107	instantiation	119, 120	⊢
	: , : , :
108	instantiation	121, 122, 123, 124^*	⊢
	: , :
109	instantiation	199, 174, 125	⊢
	: , : , :
110	instantiation	199, 174, 198	⊢
	: , : , :
111	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.nonzero_if_is_nat_pos
112	conjecture		⊢
	proveit.numbers.multiplication.mult_neg_right
113	instantiation	126, 147	⊢
	:
114	instantiation	127, 128, 129	⊢
	: , : , :
115	conjecture		⊢
	proveit.numbers.exponentiation.neg_power_as_div
116	instantiation	199, 130, 131	⊢
	: , : , :
117	instantiation	132, 133	⊢
	:
118	instantiation	199, 168, 134	⊢
	: , : , :
119	axiom		⊢
	proveit.logic.equality.substitution
120	instantiation	135, 136	⊢
	:
121	conjecture		⊢
	proveit.numbers.negation.distribute_neg_through_binary_sum
122	instantiation	199, 160, 137	⊢
	: , : , :
123	instantiation	199, 160, 138	⊢
	: , : , :
124	instantiation	139, 140	⊢
	:
125	conjecture		⊢
	proveit.physics.quantum.QPE._two_pow_t_is_nat_pos
126	conjecture		⊢
	proveit.numbers.multiplication.elim_one_right
127	axiom		⊢
	proveit.logic.equality.equals_transitivity
128	instantiation	141, 142, 185, 196, 143, 144, 147, 148, 145	⊢
	: , : , : , : , : , :
129	instantiation	146, 147, 148, 149	⊢
	: , : , :
130	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_nonzero_within_complex_nonzero
131	instantiation	199, 150, 151	⊢
	: , : , :
132	conjecture		⊢
	proveit.numbers.exponentiation.complex_x_to_first_power_is_x
133	instantiation	199, 160, 152	⊢
	: , : , :
134	instantiation	199, 178, 153	⊢
	: , : , :
135	conjecture		⊢
	proveit.numbers.multiplication.elim_one_left
136	instantiation	199, 160, 154	⊢
	: , : , :
137	instantiation	199, 168, 155	⊢
	: , : , :
138	instantiation	199, 168, 156	⊢
	: , : , :
139	conjecture		⊢
	proveit.numbers.negation.double_negation
140	instantiation	199, 160, 157	⊢
	: , : , :
141	conjecture		⊢
	proveit.numbers.addition.disassociation
142	axiom		⊢
	proveit.numbers.number_sets.natural_numbers.zero_in_nats
143	conjecture		⊢
	proveit.core_expr_types.tuples.tuple_len_0_typical_eq
144	instantiation	158	⊢
	: , :
145	instantiation	199, 160, 159	⊢
	: , : , :
146	conjecture		⊢
	proveit.numbers.addition.subtraction.add_cancel_triple_13
147	instantiation	199, 160, 171	⊢
	: , : , :
148	instantiation	199, 160, 161	⊢
	: , : , :
149	instantiation	162	⊢
	:
150	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_nonzero_within_real_nonzero
151	instantiation	199, 163, 164	⊢
	: , : , :
152	instantiation	199, 168, 165	⊢
	: , : , :
153	instantiation	199, 166, 167	⊢
	: , : , :
154	instantiation	199, 168, 169	⊢
	: , : , :
155	instantiation	199, 178, 187	⊢
	: , : , :
156	instantiation	199, 178, 188	⊢
	: , : , :
157	instantiation	180, 181, 201	⊢
	: , : , :
158	conjecture		⊢
	proveit.numbers.numerals.decimals.tuple_len_2_typical_eq
159	instantiation	170, 171	⊢
	:
160	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_within_complex
161	instantiation	199, 172, 173	⊢
	: , : , :
162	axiom		⊢
	proveit.logic.equality.equals_reflexivity
163	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.nonzero_int_within_rational_nonzero
164	instantiation	199, 174, 175	⊢
	: , : , :
165	instantiation	199, 178, 176	⊢
	: , : , :
166	instantiation	177, 179, 194	⊢
	: , :
167	assumption		⊢
168	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_within_real
169	instantiation	199, 178, 179	⊢
	: , : , :
170	conjecture		⊢
	proveit.numbers.negation.real_closure
171	instantiation	180, 181, 182	⊢
	: , : , :
172	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.real_neg_within_real
173	instantiation	199, 183, 184	⊢
	: , : , :
174	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_pos_within_nonzero_int
175	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat2
176	instantiation	199, 195, 185	⊢
	: , : , :
177	conjecture		⊢
	proveit.numbers.number_sets.integers.int_interval_within_int
178	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.int_within_rational
179	instantiation	186, 187, 188	⊢
	: , :
180	theorem		⊢
	proveit.logic.sets.inclusion.unfold_subset_eq
181	instantiation	189, 190	⊢
	: , :
182	axiom		⊢
	proveit.physics.quantum.QPE._t_in_natural_pos
183	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_neg_within_real_neg
184	instantiation	199, 191, 192	⊢
	: , : , :
185	conjecture		⊢
	proveit.numbers.numerals.decimals.nat2
186	conjecture		⊢
	proveit.numbers.addition.add_int_closure_bin
187	instantiation	193, 194	⊢
	:
188	instantiation	199, 195, 196	⊢
	: , : , :
189	theorem		⊢
	proveit.logic.sets.inclusion.relax_proper_subset
190	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.nat_pos_within_real
191	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.neg_int_within_rational_neg
192	instantiation	197, 198	⊢
	:
193	conjecture		⊢
	proveit.numbers.negation.int_closure
194	instantiation	199, 200, 201	⊢
	: , : , :
195	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_within_int
196	theorem		⊢
	proveit.numbers.numerals.decimals.nat1
197	conjecture		⊢
	proveit.numbers.negation.int_neg_closure
198	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat1
199	theorem		⊢
	proveit.logic.sets.inclusion.superset_membership_from_proper_subset
200	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_pos_within_int
201	conjecture		⊢
	proveit.physics.quantum.QPE._two_pow_t_minus_one_is_nat_pos
^*equality replacement requirements