Our work concerns Frege systems, substitution Frege systems (sF), renaming Frege systems, top/bottom-Frege systems and extended Frege systems (eF). Urquhart shows that tautologies associated to a binary strings require Omega(n/log n) lines to be proved in sF. Here we prove, by giving a sF proof of O(n/log n) lines in substitution Frege, that his lower bound is optimal and we show that in the tree-like case Omega(n) lines are required for a proof of the same tautologies. We also show the following two simulation results: (1) tree-like substitution Frege p-simulates non tree-like substitution Frege; (2) Tree-like Frege linearly simulates tree-like renaming Frege and tree-like top/bottom-Frege.